BOJ_2294_동전2

이번에 풀어 볼 문제는 동전2 문제입니다.

문제부터 확인하겠습니다.

여기서 중요한 것은 다양한 종류의 동전으로 금액을 만들 때, 다양한 동전을 기준으로 금액을 만들어 내야 한다는 것입니다.

동전을 기준으로 진행될 경우 발생할 수 있는 경우의 수가 중복되지 않는다는 점입니다.

가령 4라는 숫자를 1,2,3 이 세 가지 수로 만든다고 할 때,

4를 기준으로 1,2,3을 만든다면

---

1+1+1+1

1+1+2

1+2+1

2+1+1

2+2

1+3

3+1

---

다음과 같이 총 7가지의 경우가 나오게 됩니다.

하지만 1,2,3 즉, 4를 만들어 내야할 요소들의 갯수(3가지)를 기준으로 4를 만들게 된다면,

1+1+1+1

1+1+2

1+3

2+2

다음과 같이 4가지 경우가 나오게 됩니다.

방법에 대한 경우의 수가 중복되지 않아서 생기는 특징이라고 볼 수 있습니다.

다음은 그 동안 해왔듯이, 점화식을 세워보겠습니다.

D[i] 는 여러 동전들을 가지고 i원을 만드는 방법인데, 사용하는 동전의 갯수가 최소인 경우라고

정의하겠습니다.

이렇게 진행한다면 점화식은 다음과 같습니다.

D[i] = min(D[i],D[i-A[j]]); 

(A[j] 는 금액이고 j의 값은 동전의 갯수로 표현할 수 있습니다. (방법이 우선이 되어야 중복이 안생긴다.))

따라서 동전의 갯수 ( 동전의 수로 만들 수 있는 방법의 수 ) : n 이라 하고 목표 금액을 k라고 한다면,

코드는 다음과 같습니다.

---

for(int i=1 ; i <= n ; i++){

for(int j=0; j <= k ; j++){

if(j-a[i] >= 0 && d[j - a[i]] != -1){

if(d[j] == -1 || d[j] > d[j-a[i]] + 1){

d[j] = d[j-a[i]] + 1;

}

}

}

}

---

추가 설명을 하자면 처음 if 조건문에서 j-a[i] >= 0은 Memorization에 속하는 조건이며,

(메모를 하기 위해선 0보다 크거나 같아야함)

d[j-a[i]] != -1 이라는 조건은 점화식을 세울 때 d[j] 보다 앞서 있는 것이 d[j-a[i]] 이고, 

해당 값이 방문하지 않았다고 (방문을 안할 경우 -1 // -1로 초기화 했기 때문) 말할 수 없으므로 

다음과 같은 조건을 내세운 것입니다.

이 두 조건은 동시에 만족해야만 하기 때문에 'AND 연산자' 를 활용하여 조건을 만들었습니다.

두 번째 if 조건문에서는 앞으로 방문할 d[j] 값이 -1이어야 하는데, 이는 필수 조건이 아닙니다.

왜냐하면 최소 조건을 토대로 d[j] 값이 계속해서 바뀔 것이기 때문입니다.

또한 그 다음 조건 (d[j] > d[j-a[i]] + 1)은 경우의 수 중 최소 값을 구하기 위해서

세운 조건입니다. 

이러한 조건이 만족하는 경우 d[j] = d[j-a[i]] + 1로 d[j] 값을 정의해줍니다.

전체 코드는 다음과 같습니다. 

---

import java.util.Scanner;

public class 동전2 {

private static Scanner scanner;

private static int[] d; // 경우의 수

private static int[] a; // 금액의 가치

public static void main(String[] args) {

// TODO Auto-generated method stub

scanner = new Scanner(System.in);

int n = scanner.nextInt();

int k = scanner.nextInt();

a = new int[n + 1];

for (int i = 1; i <= n; i++)

a[i] = scanner.nextInt();

d = new int[k + 1];

for (int i = 0; i <= k; i++) {

d[i] = -1;

}

d[0] = 0;

for (int i = 1; i <= n; i++) {

for (int j = 0; j <= k; j++) {

if (j - a[i] >= 0 && d[j - a[i]] != -1) {

if (d[j] == -1 || d[j] > d[j - a[i]] + 1) {

d[j] = d[j - a[i]] + 1;

}

}

}

}

System.out.println(d[k]);

}

}

---

감사합니다.