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

문제 : https://www.acmicpc.net/problem/2293

2293번: 동전 1

 

어떤 문제인가?

n가지의 동전이 있다.

이 때 n가지 동전을 사용해서 k원을 만드는 경우의 수를 구하는 것이다.

 

 

접근 방법

이 문제를 dp를 사용해 접근하였다.

 

문제의 예시로 알아보자.

 

1, 2, 5원짜리 동전으로 10원을 만드는 경우의 수다.

 

1원

1

 

2원

1 1

2

 

3원

1 1 1

2 1

 

4원

1 1 1 1

2 1 1

2 2

 

5원

1 1 1 1 1

2 1 1 1

2 2 1

5

 

어떤 규칙이 보이나요?

 

3원을 만든다고 했을 때,

1원으로만 만드는 방법, 2원과 1원으로 만드는 방법 두 가지가 있다.

 

4원은

1원으로만 만드는 방법, 2원과 1원으로 만드는 방법, 2원으로만 만드는 방법 세 가지가 있다.

 

보면 4원을 만들 때, 4원에서 2원을 뺀 2원을 만드는 방법의 개수를 더 했다.

그렇게 점점 n원을 만드는 방법의 개수가 증가하는 것이다.

 

메모이제이션

 

n원을 1원으로 만드는 방법 1가지

 

n(n>=2)원을 2원으로 만드는 방법은, n-2원을 만드는 방법을 기존 메모이제이션 되어있는 값에 더한다.

 

n(n>=5)원을 5원으로 만드는 방법은, n-5원을 만드는 방법을 기존 메모이제이션 되어있는 값에 더한다.

 

모든 계산을 메모이제이션이 끝나고 나면 n원을 만드는 방법이 저장되어 있을 것이다.

 

int coin[101];
int dp[10001];

동전을 저장할 배열과 dp값을 저장할 배열을 저장한다.

 

int n, k;
cin >> n >> k;

문제의 조건대로 변수들을 입력 받는다.

 

for (int i = 0; i < n; i++) {
    cin >> coin[i];
}

동전을 입력 받는다.

 

dp[0] = 1;

0원을 만드는 방법은 아무것도 선택하지 않은 한가지 이다.

dp [ i  ] = x 은

i원을 만드는 방법은 x개라는 뜻이다.

 

for (int i = 0; i < n; i++) {
    for (int j = coin[i]; j <= k; j++) {
        dp[j] += dp[j - coin[i]];
    }
}

모든 동전에 대하여 j원을 만드는 개수에 j - coin[ i ]원을 만드는 방법의 수를 계속 더해나간다.

 

그럼 k원을 만드는 방법이 계산이 되어 있을 것이다.

 

cout << dp[k];

k번째 dp값을 출력해주면 끝!

 

 

무엇이 어려웠는가?

이 문제가 여태 풀어본 dp 문제중 점화식 세우기까지 제일 오래 걸렸다...

진짜 제일 시간을 많이 쓴 것 같다.

될 듯 안 될듯,,, 정말 짜증도 많이 났지만,,,

무엇인가 되어가는 느낌이 들어서 계속 덤빌 수 있었던 것 같다.

 

수학적 사고력이 부족한 나란 녀석,,,, 어떡해,,,,

 

 

배운 점

나는 수학적 사고력이 매우 부족하다!

그래서 고등학생때 부터 점화식 세우는 걸 제일 싫어했는데..

 

다신 안 볼 줄 알았던 점화식을 다시 공부하게 될 줄 이야..

어떻게 점화식까지 사랑하겠어,,, 알고리즘을 사랑하는 거지,,,

 

점화식의 정해진 틀도 없다보니 너무 어렵다.. 

 

https://github.com/farmJun/Algorithm_BOJ_PS/blob/main/%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9%20%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D/2293.cpp

GitHub - farmJun/Algorithm_BOJ_PS: 백준 알고리즘 문제풀이 기록 레포짓입니다.