[알고리즘] 백준 2293 c++

문제 링크

2293번: 동전 1

틀린이유

• 백트래킹으로 모든 조합을 구하는 건가.. 그러기에는 n이 너무 큰데..
  → 그 다음에 DP인가? 하는 사고로 안 감😢 모르겠다로 감..
• DP 확인 후 점화식 세우고 나서 실제 예제로 안해보고 GO 함
• New 점화식 찾기 할 때 나열해서 규칙찾았어야했는데 마구자비로 함
  

📌 백트래킹이 아닌가…ㅜㅜ라는 생각이 든 당신! → DP를 떠올려라!
📌 점화식 찾기 == 직접 해보면서 규칙 찾기

문제 분석

문제

• n가지 종류의 동전
• 각 동전의 가치는 모두 다름 (중복X)
• 각 동전은 무한개 존재
• 적당히 사용해서, 가치의 합 k가 되도록
• 구하는 것) 그 경우의 수는?

입력

• 1 ≤ n ≤ 100
• 1 ≤ k ≤ 10,000
• 1≤ 동전의 가치 ≤ 100,000

구현 방법

모든 경우의 수를 세면서 (0, 0, 0) , (0, 0, 1), (0, 0, 2) … 로 센다면 시간초과 발생

→ DP 문제임

1. 테이블 정의하기
2. 점화식 세우기
3. 초기값 설정하기

---

1. 테이블 정의하기

d[k] = 가치 합이 k일때의 경우의 수

2. 점화식 세우기

d[k] = d[k- arr[0]] + d[k-arr[1]] + … + d[k-arr[N-1]]

But k가 동전의 가치 이상일때만 점화식을 세울 수 있음

→ 동전의 가치에 따라 테이블의 값이 달라짐

→ 동전의 가치를 기준으로 테이블에 값을 채워가자

for (int i=0; i<arr.size(); i++){
	for (int k=arr[i]; k<=K; k++)
		d[k] += d[k-arr[i]];
}

3. 초기값 설정

0이 되는 방법은 모든 동전을 사용하지 않는 경우의 수이므로 d[0] = 1

전체 코드

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, K;
    cin >> N >> K;
    vector<int> arr(N);
    vector<int> d(K+1, 0);
    for (int i=0; i<N; i++) cin >> arr[i];
    
    sort(arr.begin(), arr.end());

    d[0] = 1;
    for (int i=0; i<arr.size(); i++){
        for (int k=arr[i]; k <= K; k++){
            d[k] += d[k-arr[i]];
        }
    }
    
    cout << d[K];
    //for (int i=0; i<=K; i++) cout << d[i] <<' ';
    

    return 0;
}