CS 지식 정리/코딩테스트 준비

[백준] 2293. 동전 1 (C++)

termuni 2025. 1. 9. 15:14

문제

n가지 종류 동전, 각 동전이 나타내는 가치는 다름
이 동전을 적당히 사용, 가치 합 k원 되는 경우의 수
사용 동전 구성이 같은데 순서만 다른 것 -> 같은 경우

입력

n k (1 <= n <= 100, 1 <= k <= 10000)
n1
n2
...
nn
 

예제 입력

3 10
1
2
5

 

문제 분석

이 경우 10을 만드는 경우의 수는 다음과 같습니다.
 
1 1 1 ... 1 1    → 1 10개
1 1 1 ... 1 2    → 1 8개, 2 1개
1 1 1 ... 2 2    → 1 6개, 2 2개
1 1 1 1 1 5     →  1 5개, 2 0개, 5 1개
1 1 1 1 2 2 2  → 1 4개, 2 3개, 5 0개
1 1 1 2 5        → 1 3개, 2 1개, 5 1개
1 1 2 2 2 2     →  1 2개, 2 4개, 5 0개
1 2 2 5           →  1 1개, 2 2개, 5 1개
2 2 2 2 2        → 1 0개, 2 5개, 5 0개
5 5                 →  1 0개, 2 0개, 5 2개

10가지이므로 출력은 "10"
 

그래서, 다음과 같은 방향으로 풀이를 고안해봤다!

6 20
2
3
4
5
6
7

2*0 + 3*0 + 4*0 + 5*0 + 6*0 + 7*0 = 0
2*1 + 3*0 + 4*0 + 5*0 + 6*0 + 7*0 = 2
2*2 + 3*0 + 4*0 + 5*0 + 6*0 + 7*0 = 4
2*3 + 3*0 + 4*0 + 5*0 + 6*0 + 7*0 = 6
...
2*10 + 3*0 + 4*0 + 5*0 + 6*0 + 7*0 = 20 -> Count++
2*11 + 3*0 + 4*0 + 5*0 + 6*0 + 7*0 = 22 => Over, Next
2*0 + 3*1 + 4*0 + 5*0 + 6*0 + 7*0 = 3
2*1 + 3*1 + 4*0 + 5*0 + 6*0 + 7*0 = 5
...
2*9 + 3*1 + 4*0 + 5*0 + 6*0 + 7*0 = 21 => Over, Next
2*0 + 3*2 + 4*0 + 5*0 + 6*0 + 7*0 = 6
...
2*7 + 3*2 + 4*0 + 5*0 + 6*0 + 7*0 = 20 -> Count++
2*8 + 3*2 + 4*0 + 5*0 + 6*0 + 7*0 = 22 => Over, Next
...
2*0 + 3*2 + 4*0 + 5*0 + 6*0 + 7*2 = 20 -> Count++
...
2*0 + 3*7 + 4*0 + 5*0 + 6*0 + 7*0 = 21 => Over, Next
2*0 + 3*0 + 4*1 + 5*0 + 6*0 + 7*0 = 4
...
2*1 + 3*5 + 4*1 + 5*0 + 6*0 + 7*0 = 21 => Over, Next
2*0 + 3*6 + 4*1 + 5*0 + 6*0 + 7*0 = 22 => Over, Next
2*0 + 3*0 + 4*2 + 5*0 + 6*0 + 7*0 = 8
...
2*0 + 3*0 + 4*0 + 5*0 + 6*0 + 7*3 = 21 => Over, END​

 
이렇게 해서, (최종 목표 숫자 / 제일 큰 숫자) + 1 만큼 온 경우 끝내기

-> 약 50분 걸려서 도출해낸 방법... 이나, 실제로 이 방법으로 풀이를 하였을 때, 시간 초과가 나오는 문제가.. ㅠㅜㅠ
 
이에 접근 방법이 틀린 것인지 확인하기 위해 검색해본 결과, 점화식을 활용하여 풀이하는 방향이 일반적이었다..

 

(아래는 시간 초과 된 코드)

#include<iostream>

using namespace std;

int nums[101], counts[101], num, target;

int main()
{
    //INIT
    int sum = 0, answer = 0;
    for(int i=0; i<=100; ++i)
    {
        nums[i] = 0;
        counts[i] = 0;
    }

    //Input
    cin>>num>>target;
    for(int i=0; i<num; ++i)
    {
        int temp;
        cin>>temp;
        nums[i] = temp;
    }
    
    //최대 counts의 값이 0이면 지속, 아니면 취소
    while(counts[num]==0)
    {
        sum = 0;
        //조건 따지기 위해 Sum 값을 계산
        for(int i=0; i<num; ++i)
        {
            sum += nums[i] * counts[i];            
        }

        // cout<<"Sum : "<<sum<<'\n';

        //아직 더 더해야 하는 경우
        if(sum < target)
        {
            counts[0] += 1;
        }//아직 더 더해야 하는 경우

        //그만 더해도 되는 경우
        else
        {
            answer = (sum==target) ? answer+1 : answer;
            int checker = 0;
            while(true)
            {
                if(counts[checker] != 0)    //만약 그 카운트 값이 0이 아닌 경우
                {
                    counts[checker+1] += 1;
                    counts[checker] = 0;
                    break;
                }
                else
                {
                    checker += 1;
                }
            }
        }//그만 더해도 되는지 판단

    }//전체 While

    cout<<answer<<endl;
}

찾아보니, Dynamic Programming을 바탕으로 점화식을 만들어서 푸는 접근을 권장... 이 부분 관련하여 공부하고 정리해야 할 것 같다

 

그래서 남들처럼 Dynamic Programming을 바탕으로 점화식을 세우고, 해보려고 하였으나... 인터넷 검색으로 나온 점화식이 이해가 가지 않고, 그렇다고 이걸 어떻게 점화식으로 해낼 수 있는 지 도저히 모르겠어서 G선생님의 힘을 빌렸다.

GPT 선생님의 답변

 

물론입니다! 주어진 동전 집합과 목표 금액으로 Dynamic Programming을 어떻게 적용하는지 단계별로 설명하겠습니다.

문제

  • 동전의 종류: 1원, 2원, 5원
  • 목표 금액: 10원

점화식

  1. dp[j]는 j원을 만드는 경우의 수를 저장합니다.
  2. dp[j] += dp[j - coin]는 다음을 의미합니다:
    • coin 동전을 추가했을 때 j원을 만들 수 있는 경우의 수는 j - coin원을 만드는 경우의 수를 더한 것입니다.

단계별 설명

초기화

  • dp[0] = 1: 0원을 만드는 방법은 아무 동전도 사용하지 않는 1가지 방법뿐입니다.

1. 동전 1원으로 경우의 수 채우기

동전이 1원일 때, 모든 금액을 1원 동전만으로 채울 수 있습니다.

  • dp[1] += dp[0] → dp[1] = 1
  • dp[2] += dp[1] → dp[2] = 1
  • dp[3] += dp[2] → dp[3] = 1
  • dp[4] += dp[3] → dp[4] = 1
    …
  • dp[10] += dp[9] → dp[10] = 1

dp 배열 상태 (1원 동전만 사용했을 때)

dp[0] = 1
dp[1] = 1
dp[2] = 1
dp[3] = 1
dp[4] = 1
dp[5] = 1
dp[6] = 1
dp[7] = 1
dp[8] = 1
dp[9] = 1
dp[10] = 1

2. 동전 2원으로 경우의 수 추가

이제 동전 2원을 포함해 경우의 수를 업데이트합니다.

  • dp[2] += dp[0] → dp[2] = 2
  • dp[3] += dp[1] → dp[3] = 2
  • dp[4] += dp[2] → dp[4] = 3
  • dp[5] += dp[3] → dp[5] = 3
    …
  • dp[10] += dp[8] → dp[10] = 6

dp 배열 상태 (1원과 2원 사용)

dp[0] = 1
dp[1] = 1
dp[2] = 2
dp[3] = 2
dp[4] = 3
dp[5] = 3
dp[6] = 4
dp[7] = 4
dp[8] = 5
dp[9] = 5
dp[10] = 6

3. 동전 5원으로 경우의 수 추가

이제 동전 5원을 포함해 경우의 수를 업데이트합니다.

  • dp[5] += dp[0] → dp[5] = 4
  • dp[6] += dp[1] → dp[6] = 5
  • dp[7] += dp[2] → dp[7] = 6
  • dp[8] += dp[3] → dp[8] = 7
    …
  • dp[10] += dp[5] → dp[10] = 10

최종 dp 배열 상태

dp[0] = 1
dp[1] = 1
dp[2] = 2
dp[3] = 2
dp[4] = 3
dp[5] = 4
dp[6] = 5
dp[7] = 6
dp[8] = 7
dp[9] = 8
dp[10] = 10

최종 답

  • dp[10] = 10이므로, 10원을 만드는 경우의 수는 10가지입니다.

요약

  • dp[j] += dp[j - coin]를 통해 coin 동전을 추가한 경우의 수를 업데이트합니다.
  • 동전을 하나씩 추가하면서 이전 동전 구성의 경우의 수를 누적해 갑니다.
  • 각 단계에서 이전 동전 사용 결과를 기반으로 새로운 동전을 추가하여 점진적으로 모든 경우의 수를 계산합니다.
  •  

라길래, 그러면 다음과 같은 예제는 어떻게 되는지 물어보았다.

6 20
2
3
4
5
6
7

 

GPT 선생님의 답변 2

다음 입력에 대해 점화식을 기반으로 한 초기 몇 단계 결과를 설명드릴게요.


입력:

  • 동전 종류: 2, 3, 4, 5, 6, 7
  • 목표 금액: 20

초기 상태

dp[0] = 1  // 0원을 만드는 방법은 아무 동전도 사용하지 않는 1가지
dp[1] = 0  // 1원을 만드는 방법은 없음
dp[2] = 0
dp[3] = 0
dp[4] = 0
...

첫 번째 동전: 2원

이제 동전 2원을 사용해 경우의 수를 채워 봅니다.
점화식: dp[j] += dp[j - 2]

  • dp[2] += dp[0] → dp[2] = 1
  • dp[3] += dp[1] → dp[3] = 0
  • dp[4] += dp[2] → dp[4] = 1
  • dp[5] += dp[3] → dp[5] = 0
  • dp[6] += dp[4] → dp[6] = 1
    …

현재 dp 배열 (2원 동전만 사용):

dp[0] = 1
dp[1] = 0
dp[2] = 1
dp[3] = 0
dp[4] = 1
dp[5] = 0
dp[6] = 1
...

두 번째 동전: 3원

이제 동전 3원을 추가합니다.
점화식: dp[j] += dp[j - 3]

  • dp[3] += dp[0] → dp[3] = 1
  • dp[4] += dp[1] → dp[4] = 1
  • dp[5] += dp[2] → dp[5] = 1
  • dp[6] += dp[3] → dp[6] = 2
  • dp[7] += dp[4] → dp[7] = 1
  • dp[8] += dp[5] → dp[8] = 1
  • dp[9] += dp[6] → dp[9] = 2
    …

현재 dp 배열 (2원, 3원 동전 사용):

dp[0] = 1
dp[1] = 0
dp[2] = 1
dp[3] = 1
dp[4] = 1
dp[5] = 1
dp[6] = 2
dp[7] = 1
dp[8] = 1
dp[9] = 2
...

세 번째 동전: 4원

이제 동전 4원을 추가합니다.
점화식: dp[j] += dp[j - 4]

  • dp[4] += dp[0] → dp[4] = 2
  • dp[5] += dp[1] → dp[5] = 1
  • dp[6] += dp[2] → dp[6] = 3
  • dp[7] += dp[3] → dp[7] = 2
  • dp[8] += dp[4] → dp[8] = 3
  • dp[9] += dp[5] → dp[9] = 3
    …

현재 dp 배열 (2원, 3원, 4원 동전 사용):

dp[0] = 1
dp[1] = 0
dp[2] = 1
dp[3] = 1
dp[4] = 2
dp[5] = 1
dp[6] = 3
dp[7] = 2
dp[8] = 3
dp[9] = 3
...

이 과정을 동전 5원, 6원, 7원에 대해 반복하여 최종적으로 dp[20] 값을 얻으면 원하는 결과가 됩니다.

[문제 후기]

우선, 내가 생각보다 알고리즘의 기초에 대해서 부족한 부분이 있다는 것을 알았다. DP로 접근 할 생각을 제대로 못하여, 어렵게 풀어가려고 했던 것 같다.. 다른 Dynamic Programming 문제 유형은 어떤 것이 있는지 알아보면서, 연습해야 할 것 같다.

 

다음은 GPT의 힘을 빌린 코드 예시!

#include<iostream>
#include<vector>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;  // 동전의 종류 n, 목표 가치 k
    vector<int> coins(n);
    for (int i = 0; i < n; ++i) {
        cin >> coins[i];
    }

    vector<int> dp(k + 1, 0);  // dp[i]: i원을 만드는 경우의 수
    dp[0] = 1;  // 0원을 만드는 경우는 아무 동전도 사용하지 않는 한 가지 방법
    
    for (int coin : coins) {
        for (int j = coin; j <= k; ++j) {
            dp[j] += dp[j - coin];
        }
    }

    cout << dp[k] << endl;  // k원을 만드는 경우의 수 출력
    return 0;
}

 

아래는 이걸 본 뒤, 내가 내 방식대로 다시 한 번 정리한 코드.

#include<iostream>

using namespace std;

int nums[100010];
int n, k;

int main()
{
    //INIT
    nums[0] = 1;
    for(int i=1; i<100010; ++i)
    {
        nums[i] = 0;
    }

    //INPUT
    cin >> n >> k;

    for(int i=0; i<n; ++i)
    {
        int coin;
        cin>>coin;
        nums[coin] += 1;
        for(int j = coin + 1; j <= k; ++j)
        {
            nums[j] = nums[j] + nums[j-coin];
        }
    }

    cout<<nums[k];

    return 0;
}

 

이거를 한 번 보고, 원리를 알았으니 다시 한 번 코드를 작성해보고, DP에 대해 정리해봐야겠다.

'CS 지식 정리 > 코딩테스트 준비' 카테고리의 다른 글

[백준] 1062. 가르침 (C)  (0) 2025.03.07
[공부] 순열과 조합 (C)  (0) 2025.03.06
[백준] 1038. 감소하는 수 (C)  (0) 2025.03.04
[백준] 2667. 단지 번호 붙이기 (C++)  (0) 2025.02.04
[백준] 2294. 동전 2 (C++)  (0) 2025.01.13

'CS 지식 정리/코딩테스트 준비'의 다른글

  • 현재글[백준] 2293. 동전 1 (C++)

관련글

티스토리툴바