[백준] 11052번 문제 풀이

문제를 어느정도 숙지한 다음 끙끙 앓다가 보러 온 사람이면 좋겠다.

이 문제를 30분정도 생각해보면서 문제의 해결을 위한 방법을 1가지는 생각해냈다!! 대단한 성과다..

하지만 생각한 방법을 코드화 하지 못했다.

다음 문제를 풀 때는 생각하고 있는 방법을 코드로 풀어내는 과정을 생각하면서 풀어보자.

1가지 생각한 방법이 뭐냐면 N값이 4가 들어온 다음 카드팩의 비용을 각각 1 5 3 6을 할당했다고 가정해보자. (물론 사람이 이걸 보면 문제를 이해했다는 가정하에 한 눈에 파악이 가능하다)

그렇다면 이 카드팩의 최대 비용은 10이 된다.

왜냐하면 카드팩 1장을 가격은 1원이고, 이걸 4번 구매해봤자 총 4원이다.

카드팩 2개의 가격은 5원이니 일단 하나를 구입하고, 1원짜리 카드팩 2개를 사게 되면 총 7원이다. 그리고 카드팩 2개의 가격이 5원인 것을 두개를 사게 되면 총 10원이다. 이런식으로 조금만 검사를 해보면, 5원짜리 카드팩 2개를 사는 것이 최대 비용이라는 결과를 알 수 있다.

풀이 : 
이 문제는 마지막을 먼저 생각을 하는 문제이다.
점화식 도출 과정 : 
arr[1001] = {}; // 처음에 입력받는 카드팩 a개 구입 비용을 저장하는 배열
dp[1001] = {}; // 카드팩의 최댓값을 구하기 위해 저장하는 배열

마지막에 카드 1장을 구매해야 하는 경우를 생각해보자.
처음에 N 값을 입력하고 나서 마지막에 카드 1장을 구매하는 경우를 생각해보면 DP[N - 1] + Arr[1]이 될 것이다. 그리고 마지막에 카드 2장을 구매해야 하는 경우를 생각해보면 DP[N - 2] + Arr[2]이 될 것이다. 그렇다면 이런식으로 계속 마지막에 구매해야하는 카드팩의 개수가 늘어난다면 어떻게 될까?
DP[N - A] + Arr[A]이 된다. 최종적으로 나오는 식은 다음과 같다. DP[N] = max(DP[N - A], DP[N] + Arr[A])이 된다.

이 문제가 원하는 값은 카드팩의 개수가 N값일 때 계산되어 있는 카드팩의 최대비용이다.
그래서 위의 나와있는 식처럼 max함수를 이용해서 이전에 계산해서 저장돼 있던 DP[N]과 비교를 하는 것이다.
아직까지 왜 이런식으로 점화식이 도출되는지 모르겠다.

 

코드 :

#include <iostream>
#include <algorithm>
using namespace std;

int arr[1001] = {};
int dp[1001] = {};

int main()
{
  int n;
  cin >> n;
  dp[0] = arr[0] = 0;
  for (int i = 1; i <= n; i++)
    cin >> arr[i];
  for (int i = 1; i <= n; i++)
  {
    for (int j = 1; j <= i; j++)
    {
      dp[i] = max(dp[i], dp[i - j] + arr[j]);
    }
  }
  cout << dp[n];
  return 0;
}

 

도움 된 블로그 :

yabmoons.tistory.com/23

[ 백준 11052 ] 카드 구매하기 (C++)