90951 [C] 9095: 1, 2, 3 더하기 이 문제 역시 Dynamic Programming을 이용한 문제이다. Dynamic Programming의 특징은 첫째로 문제를 작게 나누어 최대한 연산을 반복하지 않도록 하는 것이고 둘째로는 배열에 값을 저장하여 점화식을 이용하여 푸는 문제가 많은 것이다. 이 문제 역시 점화식만 잘 알 수 있었다면 쉽게 풀 수 있다. 예를 들어 4의 경우 4=1+3, 2+2, 1+3 이런식으로 표현할 수 있는데 1+3은 1+cpy[3], 2+2=2+cpy[2], 1+3=cpy[3] 으로 생각하면 4를 1,2,3으로 표현하는 모든 경우의 수를 표현할 수 있다. 이를 일반화 하면 cpy[i]=cpy[i-1]+cpy[i-2]+cpy[i-3]으로 표현할 수 있고 max를 구한 이유는 물론 이 문제는 10까지만 표현하면 되므로.. 2023. 7. 21. 이전 1 다음