[11502] 카드 구매하기 - c++

https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

정후이 폼 미쳐 따이.... 드디어... 드디어 내 혼자 힘으로 DP 문제를 풀어 버렸다... 이게 무슨 일인고

풀고 난 후에 다른 사람들 풀이를 봤을 때 좀 이상하게 푼 감이 있지만 일단 풀이를 시작하겠다!

 

---

아이디어

최근에 KnapSack문제가 인상 깊어서 그런가? 이 문제도 비슷하게 풀 수 있을 것 같았다.

• DP테이블을 이차원으로 정의
• 행(row) => i번째 카드 번호
• 열(column) => j개의 카드를 구매할때의 최댓값

점화식

$$\large dp [i][j] = max(dp [i-1][j], \;dp [i][j-i] + arr [i],\; dp [j-i][j-i] + arr [i])$$

 

---

 

dp [1][2] = max(dp [1-1][1], dp [1][1-1] + arr [1], dp[1-1][1-1] + arr[1]

= max(dp [1][1], dp [1][0]+arr [1], dp [0][0]+arr [1])

= max(1, 1+1, 0+1)

= 2

dp [2][3] = max(dp [2-1][3], dp [2][3-2] + arr [2], dp[3-2][3-2] + arr[2]

= max(dp [1][3], dp [2][1]+arr [2], dp [1][1]+arr [2])

= max(3, 0+1, 1+5)

=  6

 

---

CODE

#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}
int n;
int arr[1005];
unsigned int dp[1002][1002];

int main(){
  init();
  cin >> n;
  for(int i = 1; i <= n; ++i) cin >> arr[i];
  dp[1][1] = arr[1];

  for(int i = 1; i <= n; ++i)
    for(int j = i; j <= n; ++j)
      dp[i][j] = max({dp[i-1][j], dp[i][j-i]+arr[i], dp[j-i][j-i] + arr[i]});

  cout << dp[n][n];
  return 0;
}

다른 사람이 푼 풀이를 봤을 때 나의 풀이는 정말 비효율 적이란 걸 느꼈다.... 그렇기에 다른 사람의 풀이도 분석해 보도록 하자

---

다른 분의 풀이

• DP [ i ] = i개를 구매했을 때의 최대 값
• 1개짜리를 구매한다면 N-1개의 카드를 구매해야 함
• 2개짜리를 구매한다면 N-2 개의 카드를 구매해야 함

점화식

$$\large dp [i] = max(dp [i],\; dp [i-j] + arr [ j ])$$

---

CODE

#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}
int n;
int arr[1005];
int dp[1002];

int main(){
  init();
  cin >> n;
  for(int i = 1; i <= n; ++i) cin >> arr[i];
  dp[1] = arr[1];
  for(int i = 2; 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;
}

그들은 천재다

---

문제를 풀며

DP문제들을 많이 풀어서 그런가 예전에 사용했던 아이디어들이 조금씩 떠오른다.

예전에 풀 때는 지옥 같았던 DP가 아직도 지옥이긴 하다.

그래도 성장한 게 눈에 보여서 기분이 좋다.

하나 풀었다고 자만하지 말자 더 성장하자 화이텐