[2294] 동전 2 - C++

안 좋은 풀이와 좋은 풀이 두 가지 다 보여 드리겠습니다.

---

안 좋은 풀이

DP테이블을 이차원 배열로 놓고 풀었다.

행 ( row ) = 내가 가진 동전의 순서

열 ( column ) = 만들 수 있는 임의의 가치

 

먼저 코드를 보고 그림으로 이해해 보도록 하자

//상수
#define MAX 2E+9

//변수들
int n, k;
int coin[101];
int dp[101][10'002];

//입력
cin >> n >> k;
  for(int i =1; i <= n; ++i)
    cin >> coin[i];

//실행 로직
for(int i = 1; i <= n; ++i){
    for(int j = coin[i]; j <= k; ++j){
      if(j-coin[i] == 0) dp[i][j] = 1;
      else{
        int mins = MAX;
        for(int u = 1; u <= i; ++u)
          mins = (dp[u][j-coin[i]] != 0 ? min(mins, dp[u][j-coin[i]]) : mins);
        dp[i][j] = mins+1;
      }
    }
  }

위 코드를 표로 그려 봤으니 천천히 따라오도록 하자

그림 설명

안 좋은 풀이 전체코드

 

#include <bits/stdc++.h>
#define MAX 2E+9

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int n, k;
int coin[101];
int dp[101][10'002];

int main(){
  init();
  cin >> n >> k;
  for(int i =1; i <= n; ++i)
    cin >> coin[i];
  
  for(int i = 1; i <= n; ++i){
    for(int j = coin[i]; j <= k; ++j){
      if(j-coin[i] == 0) dp[i][j] = 1;
      else{
        int mins = MAX;
        for(int u = 1; u <= i; ++u)
          mins = (dp[u][j-coin[i]] != 0 ? min(mins, dp[u][j-coin[i]]) : mins);
        dp[i][j] = mins+1;
      }
    }
  }
  int mins = MAX;
  for(int i = 1; i <= n; ++i)
    mins = (dp[i][k] == 0? mins : min(dp[i][k], mins));
  cout << (mins == MAX? -1 : mins); 
  return 0;
}

저어엉말 비효율 적인 방법이다.

사실 나는 이것밖에 생각나지 않았다.

그럼 안 좋은 풀이를 보았으니 어서 좋은 풀이를 보도록 하자

 

---

좋은 풀이

#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[10005], dp[10005];
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  for (int i = 0; i < n; i++)
    cin >> a[i];
  fill(dp, dp + 10005, 100005);
  dp[0] = 0;
  for (int i = 0; i < n; i++)
    for (int j = a[i]; j <= k; j++)
      dp[j] = min(dp[j], dp[j - a[i]] + 1);
  cout << (dp[k] == 100005 ? -1 : dp[k]) << '\n';
}

이 코드는 설명하지 않아도 이해할 수 있는 코드다, 이런 게 정말 맛있는 코드가 아닐까

어찌 처음부터 나올 수 있는 최대값을 미리 넣고 시작할 생각을 하였는 가

---

문제를 풀며

DP문제는 사람의 상상력을 자극시켜 여러 가지 풀이 방법이 나오는 것 같다.

DP는 테이블에 의미를 부여한다.

 

사실 동전 1을 풀때 아까 보여준 안 좋은 풀이의 방법을 사용하려 했다가 실패했었는데 여기서 사용하게 되니 기쁘지만

96ms는 너무 하자나....

 

항상 배우려는 마인드로 임하자, 나의 풀이가 맞았더라도 다른 사람의 풀이를 보며 배울 것은 얻어가자

 

 

참고 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/2294.cpp