[BOJ] 백준 2294 동전 2 / 동적 계획법(Dynamic-Programming)

이미지를 클릭하면 문제 사이트로 이동합니다.

---

 

💣 문제 이해

 

1. n가지 종류의 동전이 주어진다.

2. 이 동전들을 사용해서, 그 가치의 합이 k원이 되야한다.

3. 위 조건을 만족하는 최소의 동전의 개수를 구하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

4. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

 

동적 계획법(Dynamic Programming) 방식을 사용했다.

 

 

 

💭 풀이 과정

 

 

<coinArr>

 

1

5

12

coinArr은 동전 가치를 저장하는 배열 이다.

주어진 동전 종류는 1, 5, 12 세 가지 이다.

 

이때 std::sort 함수를 사용해서 동전 종류를 오름차순 정렬 해둔다.

 

 

 

 

<dp>

 

0

초기값

초기값

초기값

초기값

초기값

초기값

초기값

초기값

초기값

초기값

초기값

초기값

초기값

초기값

초기값

dp 는 인덱스가 값이고 그 값을 채울 수 있는 최소 동전 개수로 채워지는 배열 이다.

dp[0] 은 0 으로 초기화하고, 나머지는 987654321(초기값) 이라는 값으로 초기화 함으로, 그 인덱스에 해당하는 값이 가진 동전으로 만들 수 있는 값인지를 확인할 수 있다.

(불가능한 값이라면 987654321 이 그대로 남아있게 된다.)

 

 

 

 

 

첫 번째 동전 가치인 1의 경우를 따져보겠다. coinArr[0]

 

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

 

j - coinArr[i] 연산을 통해서, 현재 인덱스에서 현재 동전가치를 차감했을 때, (하나 추가한다는 상황) 차액이 remain 에 저장된다.

인덱스가 3인 경우를 예로 들자면, j 는 3이고, coinArr[i]는 1이다. 그러므로 remain 은 2가 된다.

 

dp[j] = std::min(dp[j], 1 + dp[remain])

이 연산을 보면, 결국 현재 인덱스에 해당하는 값을 만들 수 있는 동전 최소 개수 (dp[j]) 는 현재 동전을 빼고 계산하는 경우 (dp[j]) 와, 현재 동전을 포함하는 경우 (1 + dp[remain]) 중 더 작은 값으로 대체되게 된다.

인덱스 3의 경우는, 이전 값인 987654321 와, 현재 값인 1 + dp[2] = 3 중 최소 값인 3 이 저장된다.

 

 

 

 

 

동전 가치 5의 경우 ( coinArr[1] )

 

0

1

2

3

4

1

2

3

4

5

2

3

4

5

6

3

 

 

 

 

동전 가치 12의 경우 ( coinArr[2] )

 

0

1

2

3

4

1

2

3

4

5

2

3

1

2

3

3

 

마지막의 경우, 기존 dp[15] 가 3 이었고, 새롭게 계산한 1 + dp[3] 이 4 이므로 최소 값인 3이 저장된다.

 

마지막 삼항연산자 연산을 통해, 마지막 값이 처음 그대로 987654321 이라면 현재 가진 동전으로 만들 수 없다고 판단하여 -1 을 출력하고, 값이 변경되었다면 그 값이 최종 답으로 판단하여 그 값을 출력한다.

 

즉, 문제에 주어진 테스트케이스는 답이 3이 출력된다.

 

작성한 소스코드는 다음과 같다.

 

 

 

작성 언어: C++

 

#include <cstdio>
#include <algorithm>

int main(){
    int coinNum, priceNum;
    int coinArr[101] = {0, };
    int dp[10001] = {0, };
    scanf("%d %d", &coinNum, &priceNum);
    
    for (int i = 0; i < coinNum; ++i) {
        scanf("%d", &coinArr[i]);
    }
    std::sort(coinArr, coinArr+coinNum); // 입력받은 동전가치 오름차순 정렬
    dp[0] = 0;
    
    for (int i = 1; i <= priceNum; ++i) {
        dp[i] = 987654321;
    }
    
    for (int i = 0; i < coinNum; ++i) {
        for (int j = coinArr[i]; j <= priceNum; ++j) {
            int remain = j - coinArr[i];
            dp[j] = std::min(dp[j], 1 + dp[remain]);
        }
    }
    
    printf("%d\n", dp[priceNum] == 987654321 ? -1 : dp[priceNum]);
    return 0;
}

 

 

 

🏆 배운 점

 

처음에는 dp 배열을 2차원 배열로 선언하여, 입력으로 받은 동전 가치마다 각각 한 열씩 하여 계산했다.

문제에 나온 테스트케이스도 정답으로 나오고, 내가 만든 테스트케이스도 다 예상되는 정답이 나오나, 제출하면 계속해서 오답이 나왔다.

 

다른 사람들의 풀이를 참고하니, 1차원 배열로 선언하여도 더욱 간단하게 처리할 수 있었다.

나 역시도 1차원 배열로 다시 짜보니 한번에 정답처리를 받았다..

 

다른 날 2차원 배열로도 처리하는 연습을 해봐야겠다.