본문 바로가기

Programming Problems/Digits

홀수와 짝수의 합이 같은 정수의 갯수 세기

제곧내. n  자릿수 보다 작은 홀수와 짝수의 합이 같은 정수의 갯수를 세보자.


DP를 사용해보자.


완전탐색에서 시작해 보자.


int countsame(int curr){

if(curr>n) return 0;

int ret = 0;

curr *= 10;

for(int i = 0 ; i < 9 ; i++){

if(isequal(curr+i)) ret = ret + 1 + countsame(curr+i);

else ret = countsame(curr+i);

}

return ret;

}


NlogN 알고리즘인듯. isequal이 logN짜리라서;


근데 저렇게 하면 중복이 있을꺼같다..


n자릿수 기준으로 만들어 보자


int countsame(int curr, int n , int odd, int even){

if(curr==n) return 0;

int ret = 0;

if(odd==even) ret++;

for(int i = 0 ; i < 10 ; i++){

if(curr%2==0){

ret += countsame(curr,n,odd+i,even);

}else{

ret += countsame(curr,n,odd,even+i);

}

}

return ret;

}