[백준] 단계별로 풀어보기(단계:23,동적 계획법 2,JAVA)2293번, 동전 1

문제 링크

2293번: 동전 1

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

동적계획법이란 위 문제와 같이 동일한 연산을 계속 반복하여 비효율적으로 코드가 실행되어 그것을 향상시키기 위하여반복되는 연산의 결과를 따로 저장하여 적재적소에 코드가 더 효율적으로 만드는 방법입니다.

이 문제에서 핵심은

1. 각각의 동전은 몇 개라도 사용할 수 있다.

2. 순서만 다른 것은 같은 경우로 취급한다.

이번 문제에서 사용한 DP[i]는 가치가 i일 때 가지고 있는 동전으로 만들 수 있는 경우의 수를 저장하였습니다.

예를 들어 사용할 수 있는 동전은 2이고 만들어야 할 가치는 8일때 DP[]를 표로 표현하면

1	2	3	4	5	6	7	8
0	1	0	1	0	1	0	1

검은색 : 인덱스(가치), 빨간색 : 만들 수 있는 경우의 수

 

각 동전으로 만들 수 있는 경우의 수를 확인해보도록 하겠습니다.예제입력1을 바탕으로 표를 통해 보여드리겠습니다.

1. 동전 1로 가치를 표현할 때 경우의 수 DP[]

1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1

2. 동전 1,2로 가치를 표현할 때 경우의 수 DP[]

1	2	3	4	5	6	7	8	9	10
1	2	2	3	3	4	4	5	5	6

3. 동전 1, 2, 5으로 가치를 표현할 때 경우의 수 DP[]

1	2	3	4	5	6	7	8	9	10
1	2	2	3	4	5	6	7	8	10

위 과정을 살펴보면 공식이 하나 성립됩니다.

DP[i] = DP[i] + DP[i-해당 동전 가치]

예를들어 3. 에 8의 가치의 경우의 수를 보면

DP[8] = DP[8] + DP[8-5] = 5 + 2 = 7로 변환되는 것을 볼 수 있습니다.

이 공식이 성립하는 이유는 반복문으로 진행될 것이기 때문에 해당 가치보다 작은 가치들은 이미 1, 2, 5 동전으로 경우의 수를 구한 것이고 (i-해당 동전 가치)를 하는 것은 해당 동전을 1번은 무조건 사용하는 경우의 수를 구하는 것이기 때문입니다. 

 

마지막으로 DP[0] = 1로 초기화를 진행해주어야 합니다.

DP[0]은 i - 해당 동전 가치 = 0 이 되면 동전의 가치와 만들어야 하는 가치가 같으므로 해당 동전만 사용하면 가치가 만들어지기 때문에 경우의 수 1개로 표현할 수 있기 때문입니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. DP[0]의 값을 1로 초기화해줍니다.

2. DP[]에서 들어온 동전순으로 포함시켜서 경우의 수를 점차 늘려갑니다.

3. 모든 동전으로 경우의 수를 구한 뒤에 DP[k]값을 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 coin배열을 초기화해주었습니다.
• 동전으로 가치를 만들 수 있는 경우의 수를 구하는 coinCheck 함수를 만들었습니다.
• BufferedWriter에 k의 가치를 만들 수 있는 경우의 수 DP[k]를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• coinCheck은 반복문으로 동전 순서대로 포함시켜서 DP[i] = DP[i] + DP[i - 해당 동전 가치]로 경우의 수를 구하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int[] coin;	//동전의 가치 저장 배열
	public static int[] DP;		//가치를 만들 수 있는 경우의 수 저장 배열
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //--------입력값 저장 및 배열 초기화------------
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	int n = Integer.parseInt(st.nextToken());
    	int k = Integer.parseInt(st.nextToken());
    	DP = new int[k+1];
    	coin = new int[n];
    	for(int i=0;i<n;i++) {
    		coin[i] = Integer.parseInt(br.readLine());
    	}
    	
    	DP[0] = 1;		//DP[0]을 1로 초기화
    	coinCheck(n,k);		//함수 실행
    	bw.write(DP[k] + "\n");		//경우의 수 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    	
    }
    //--------동전으로 가치를 만들 수 있는 경우의 수 구하는 함수---------
    public static void coinCheck(int n, int k) {
    	for(int i=0;i<n;i++) {
    		for(int j=coin[i];j<=k;j++) {
    			DP[j] += DP[j-coin[i]];		//DP[i] = DP[i] + DP[i-해당 동전 가치]
    		}
    	}
    	return;
    }
}