[백준, Java] 1943번, 동전 분배(DP)

문제 링크

1943번: 동전 분배

---

주의사항

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

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

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. 동전의 가치와 개수가 주어집니다.

2. 해당 동전들의 가치를 동일하게 나누어야 합니다.

3. 동일하게 나누면 1, 아니면 0을 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2.  점화식을 통해서 동전을 동일한 가치를 나눌 수 있는지 확인합니다.

 

3. 탐색을 통해 동일한 가치로 나눌 수 있는 여부를 결과로 출력합니다.

 

 

동일한 가치로 동전 나누기(DP)

 

먼저, 동전의 가치를 동일하게 나누려면, 모든 동전 가치의 합이 짝수이어야 합니다.

→ 홀수일 때에는 반으로 나눌 수 없기 때문입니다.

 

 

동전 가치의 합이 짝수일 때, 동전의 가치를 {동전의 가치의 합 ÷ 2}만들 수 있다면 동일한 가치로 나눌 수 있다는 것입니다

 

각 동전들을 순서대로 사용하면서 동전의 가치가 발생할 수있는 경우의 수를 찾습니다.

 

경우의 수에서 {동전의 가치의 합 ÷ 2}을 만들 수 있는지 확인하는 것이 핵심입니다.

 

 

재귀를 통해서 구현을 할 수 있지만, 해당 방법을 진행하면 중복된 탐색이 매우 많이 발생하여 시간 초과가 발생할 것입니다.

 

중복된 탐색을 방지하기 위해서 가치를 만들 수 있는 여부를 DP[][]의 저장하여 탐색하는 방법으로 진행하였습니다.

 

 

DP[i][j] = i번째 동전까지 사용하였을 때 동전의 가치 j을 만들 수 있는지 여부

 

True : 만들 수 있다.

 

False : 만들 수 없다.

 

DP[0][0] = True → 동전을 사용하지 않고 만들 수 있는 가치는 0 밖에 없습니다.

 

이후, 다음 동전들을 사용할 때에는 개수를 순서대로 적용시키면서 만들 수 있는 가치를 탐색합니다.

 

예를 들어, 1번째 동전의 가치가 100이고, 3개 있을 때

 

DP[i-1][0~j]에서 True인 값은 DP[0][0] 밖에 존재하지 않습니다.

 

해당 가치에서 순서대로 동전을 사용해보면

 

DP[1][0] = True

 

DP[1][100] = True

 

DP[1][200] = True

 

DP[1][300]  = True

 

으로 변경되게 됩니다.

 

점화식으로 표현하면,

 

i번째 동전을 사용할 때

 

DP[i-1][0 ~ j] = True일 때

 

DP[i][j+({0~k} * 동전의 가치}] = True

 

→ i - 1번째 동전을 사용했을 때 만들 수 있는 가치에 i번째 동전 사용해서 가치 만들기.

 

※  k : 해당 동전의 개수

 

 

위 점화식을 모두 진행하였을 때 DP[N][동전의 가치의 합 ÷ 2] = True이면 동일한 가치로 나눌 수 있다고 판단하는 것입니다.

 

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

※테스트 케이스 2번만 진행하도록 하겠습니다.

 

N = 3

 

	가치	개수
동전 1	100	2
동전 2	50	1
동전 3	10	5

 

 

2. 점화식을 통해서 동전을 동일한 가치를 나눌 수 있는지 확인합니다.

 

 

동전 가치의 합 : 100 x 2 + 50 x 1 + 10 x 5 = 200 + 50 + 50 = 300

 

동전의 가치의 합이 홀수가 아니기 때문에 동일한 가치로 나눌 수 있는 가능성이 존재합니다.

 

 

DP[][] 점화식 진행

 

DP[0]0] = True

 

 

1번째 동전 사용

 

 

DP[1][0] = True

 

DP[1][100] = True

 

DP[1][200] = True

 

 

2번째 동전 사용

 

 

DP[2][0] = True

 

DP[2][50] = True

 

DP[2][100] = True

 

DP[2][150] = True

 

DP[2][200] = True

 

DP[2][250] = True

 

 

3번째 동전 사용

 

DP[3][0] = True

 

DP[3][10] = True

 

DP[3][20] = True

 

DP[3][30] = True

 

DP[3][40] = True

 

DP[3][50] = True

 

DP[3][60] = True

 

DP[3][70] = True

 

DP[3][80] = True

 

DP[3][90] = True

 

DP[3][100] = True

 

DP[3][110] = True

 

DP[3][120] = True

 

DP[3][130] = True

 

DP[3][140] = True

 

DP[3][150] = True

 

DP[3][160] = True

 

DP[3][170] = True

 

DP[3][180] = True

 

DP[3][190] = True

 

DP[3][200] = True

 

DP[3][210] = True

 

DP[3][220] = True

 

DP[3][230] = True

 

DP[3][240] = True

 

DP[3][250] = True

 

DP[3][260] = True

 

DP[3][270] = True

 

DP[3][280] = True

 

DP[3][290] = True

 

DP[3][300] = True

 

 

점화식 종료.

 

 

 

 

3. 탐색을 통해 동일한 가치로 나눌 수 있는 여부를 결과로 출력합니다.

 

DP[3][300 ÷ 2] = DP[3][150] = True이기 때문에 동일한 가치로 나눌 수 있습니다.

 

 

1 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 이용해서 동전의 정보를 띄어쓰기 기준 나누었습니다.
• 점화식을 통해 DP[][]의 동전 가치 만들 수 있는 여부를 저장합니다.
• 점화식 진행이 끝났을 때 DP[N][동전 가치의 합 ÷ 2]를 통해 만들 수 있는 여부 정보를 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
    static class Coin{
        int price, amount;
        public Coin(int price, int amount) {
            this.price = price;
            this.amount = amount;
        }
    }
    static Coin[] coins;
    static boolean[][] DP;
    static final int MAX_PRICE = 100000;
    static int N;

    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        //각 테스트 케이스 진행
        for (int tc = 0; tc < 3; tc++) {
            N = Integer.parseInt(br.readLine());
            coins = new Coin[N];
            int sum = 0;
            //동전 정보 저장 및 동전 가치의 합 구하기
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                int price = Integer.parseInt(st.nextToken());
                int amount = Integer.parseInt(st.nextToken());
                coins[i] = new Coin(price, amount);
                sum += price * amount;
            }
            //동전 가치의 합이 홀수일 때 : 동일한 가치 나누기 X
            if (sum % 2 == 1)
                bw.write("0");
            else {		//동전 가치의 합이 짝수일 때
                //목표 동전 가치를 위해 나누기 2 진행
                sum /= 2;
                DP = new boolean[N+1][sum+1];
                //동전을 사용하지 않았을 때
                DP[0][0] = true;
                //점화식 진행
                for(int i=1;i<=N;i++){
                    Coin cur = coins[i-1];
                    for(int j=0;j<=sum;j++){
                        //i-1개로 해당 동전의 가치를 만들 수 있을 때
                        if(DP[i-1][j]){
                            //동전 0 ~ k개 사용해보기
                            for(int k=0;k<=cur.amount;k++){
                                int tempAmount = j + cur.price * k;
                                if(tempAmount <= sum){
                                    DP[i][tempAmount] = true;
                                }
                            }
                        }
                    }
                }
                //만약 DP[N][동전 가치의 합 / 2]을 만들 수 있을 때
                if (DP[N][sum])
                    bw.write("1");
                else		//만들 수 없을 때
                    bw.write("0");
            }
            bw.newLine();
        }
        bw.flush();	//결과 출력
        bw.close();
        br.close();
    }
}