It is possible to write ten as the sum of primes in exactly five different ways:
7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2
What is the first value which can be written as the sum of primes in over five thousand different ways?
10을 소수의 합으로 나타내는 데에는 다음과 같이 5가지 방법이 있다:
7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2
소수의 합으로 5천가지 이상의 방법으로 표현 가능한 첫 숫자는 무엇인가?
--------------------------------------------------------------------------
31번 문제, 76번 문제를 조금 변형시켜 만들어진 문제이지만, 슬프게도 31번 문제, 76번 문제를 해결하는데 사용한 방법을 적용할 수 없었다. 31번 문제는 동전 숫자를 알아서 반복문을 중첩시켜 해결했고, 76번 문제는 정수론에 있는 분할수 공식을 이용해서 구했는데 이 두가지와는 성격이 달라 그대로 적용할 수 없었다.
영문 위키 Partition(Number Theory) 항목의 Restrcted partition을 잘 이해하면 적용 가능할 것 같은데 이제는 중학교 수준 이하의 실력을 가진 상황에 그 부분을 이해하고 프로그래밍 하는 것이 쉽지 않았다.
그래서, 31번, 76번 문제 모두에 적용가능했던 동적 프로그래밍 방법을 가져와 소수에 맞게 조금 응용해서 해결했다. 정답을 맞췄지만 내 것으로 소화한 것이 아니어서 찝찝함이 남는다.