감사합니다! 만약 이런 문제가 나오면 최대한 점화식을 1차원으로 줄이려고 노력하면 되는건가요?

저렇게 생각하는 게 맨 처음에 편하다보니 이 문제의 풀이를 고민 하는 과정을

1. 다 찾아본다 -> 너무 오래걸리네? -> 2. 중복을 없애자 dp -> 가장 생각하기 쉬운 방법으로 구상을 해볼라 했으나 시간초과가 될 거라 예상 됨 -> 3. 점화식이 1차원으로 될까 고민

이렇게 해야하려나요ㅠㅠ 딱 보고 바로 1차원은 안떠오르다보니 질문하게 되었습니다ㅠ

dp 함수를 이해하는 데 조금 걸렸네요.

count를 돌려보니, n=1000인 경우에는 3.35억번 함수 호출을 하는군요.

n=500인 경우에는 0.42천만번 호출하고요. O(n^3)인 건 맞는 거 같네요.

dp가 제일 쉬운 방법이긴 합니다. 이런 문제는. 저 역시 dp로 구현했고요. 전형적인 냅색 문제인 거 같으니까요~

다만, 2번 과정에서 중복을 없애자!! 해서 가지치기 조건을 구현해보자~ 라고 생각하셨다면..

아래 질문에 대해서 생각을 해 보세요.

(1) 붕어빵 2개를 팔면 얻을 수 있는 이익이 100입니다. 붕어빵 3개를 팔면 50밖에 못 얻고요.

붕어빵 3개짜리는, 2개짜리를 넣을 때 보다, 이익이 작을 가능성이 크지 않을까요?

(2) 우선적으로 넣어봐야 할 붕어빵은 어떤 것일까요?

물론, 그리디로 풀라는 것은 아닙니다. 그리디로 풀릴 문제가 아니니까요.

어떻게 하면 가지치기를 더 잘 할 수 있을지 고민을 많이 해 보세요~

@chogahui05 문제를 좀 더 꼼꼼하게 분석해보고 효율적으로 풀도록 생각을 정리 해봐야 할 거 같네요ㅠㅠ 정말 감사합니다!!