17. 프로젝트 오일러 #17 : 영어 단어의 글자수 세기.
이번 문제는 문제 자체의 난이도보다는, 영어 단어를 세는 것 자체가 너무 짜증났던 문제입니다. 그리고 우리가 보통 사용하지 않는 'and'까지 쳐서 해주어야 하니까요. 답을 썼는데 계속 틀리다고 나와서, 왜 그런가 했더니, 제가 글자수 하나를 더 쳤네요. 18 과 80 때문에 둘다 그랬네요. 단순하게 8(eight) + 'teen' 과 8(eight) + 'ty' 로 해서 5+4, 5+2 했던 것이 문제였네요. 그냥 #1 부터 계속 풀어보자 생각했던터라, 이 문제를 풀고 싶지는 않았지만, 그냥 풀어 보았습니다. #include int main() { int wc[20] = { 0, 3, 3, 5, 4, 4, 3, 5, 5, 4, 3, 6, 6, 8, 8, 7, 7, 9, 8, 8 }; int wct[20..
2015. 1. 14.
14. 프로젝트 오일러 #14 : 최대 체인을 가지는 우박수 구하기
이번 문제는 동적 프로그래밍을 이용해서 작성을 하는 것이 가장 좋을 듯 합니다. 우박수를 구하다보면, 이미 전에 계산했던 우박수 체인수가 있을 수 있습니다. 그렇게 하지 않으면, 체인수가 100여개 있는데, 1,000,000까지 구한다면, 1억번정도 평균적으로 계산해야 합니다. 동적 프로그래밍을 이용하면, 이 수를 줄일 수 있습니다. 물론 수가 1이 된다는 가정하에서 이야기지만, 현재까지 예외는 없으니까요. 사실 수학적으로 1,000,000까지 우박수가 된다는 것을 확인하면, n/2로 건너뛰기를 하기 때문에 반드시 우박수가 될 수밖에 없습니다. 순수한 수학적인 증명만으로는 할 수 없지만요. 물론, 자꾸 홀수에 걸쳐서 숫자가 비대해질 수는 있습니다만, 3n+1 은 반드시 짝수가 되기 때문에 홀수가 연달아 ..
2014. 12. 30.
