반응형 sum of primes1 #77 소수들의 합(Dynamic Programming, Back tracking) 이번 문제는 난이도 25%로 설정되어 있지만, 워낙 작은 숫자들로 이루어져 있기 때문에 어렵지 않게 풀 수 있습니다. 10을 소수들의 합으로 표현한다면, 다음과 같이 총 5가지로 표현할 수 있습니다. 동일한 소수를 여러번 쓰는 것이 가능하고, 순서없는 조합으로 표현했을 때입니다. 아래와 같이 큰 소수부터 차례대로 나열할 수도 있고, 소수의 빈도만 따져도 됩니다. 이러한 경우의 수가 5,000이 넘는 가장 가장 작은 수를 찾으라는 것이 문제입니다. 사실 어떤 수가 주어졌을 때, 경우의 수를 따지는 것은 크게 어렵지 않습니다. 백트랙킹 방법을 이용해서 풀 수도 있고, 동적 프로그래밍을 이용해서 풀 수도 있습니다. 하지만 경우의 수가 특정수를 넘는 가장 작은 수를 찾는 것은 동적 프로그래밍으로는 조금 한계가 .. 2020. 1. 24. 이전 1 다음 728x90
