[C/C++] 11052: 카드 구매하기
문제를 Top-down 방식으로 이해해본 다음에 Bottom-Up 방식으로 구현을 하였다. 예를 들어 dp[n]을 구하는 경우에 dp[n]=max(dp[n]+dp[0],dp[n-1]+dp[1],dp[n-2]+dp[2],,,,,,,,,,dp[n-k]+dp[k],,,,) 형태가 된다는 것을 알 수 있다. 이때 dp[n-k]와 dp[k]일때 (n-k>=k) 최대값을 각각 구하고 있다면 dp[n-k]+dp[k]도 최댓값이 된다. 따라서 k=1에서 k=[n/2]인 자연수까지 중에서 최댓값을 구한다면 dp[n]을 구할 수 있게 된다. 그 결과 dp[1]부터 dp[n]까지 각 경우의 최댓값을 dp배열에 저장하고 이를 이용해 문제를 풀었다! 이걸 비교하는 코드는 아래와 같다. for(int i=2;i=j) { dp[i..
2023. 8. 30.
