공부중의 블로그

제곧내. 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) ..

1 112 113 >> 11311219 918 917 >> 9918917 성질 탐구 대소관계가 정해진다. 3 34 어느게 먼저? 34.3 32 어느게 먼저? 3 323 324 어느게 먼저? 324 32 324 어느게 먼저? 324 만약 긴쪽의 남은 부분에 더 큰게 하나라도 있으면 긴걸 먼저 쓴다. 물론 남기 전의 모든 값이 같을때 얘기다.자릿수가 양쪽 다 있는 경우 큰게 먼저 나오는 쪽을 먼저 쓴다. 4 111 >> 41114 115 >> 41154 415 >> 4154 4415 32 323123 이거는 즉, 3123을 끝에 놓느냐 중간에 놓느냐로 비교를 해야겠다. 이때 반복되는 부분 32와 3123을 비교해야 한다.그러면 32가 더 크다는 결론을 얻는다. 만약 32 323223 이었으면 >>32 32 ..