[BOJ/백준] 동전1 (DP)

백준 2293: 동전1
- 풀이
- 정답 코드 (DP)
마무리

이번에 소개해드릴 문제는 다이나믹 프로그래밍을 이용하여 동전의 합계를 만드는 경우의 수를 구하는 문제를 소개해드리도록 하겠습니다.

백준 2293: 동전1

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

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

풀이

이 문제는 k원이 되는 모든 경우의 수를 구하는 문제로 dfs를 생각하기 쉽습니다. 하지만 dfs로 문제를 해결하려고 하면 타임아웃이 발생하게 됩니다.

따라서 다이나믹 프로그래밍을 이용하여 다시 계산하는 시간을 제외시켜서 성능 향상 시켜야합니다.

정답 코드 (DP)

import java.io.*;

public class Boj2293 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] ins;
        ins = br.readLine().split(" ");
        int n = Integer.parseInt(ins[0]);
        int k = Integer.parseInt(ins[1]);

        int[] coins = new int[n];
        int[] mem = new int[k + 1];

        for (int i = 0; i < n; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }
        
        // 0원을 만드는 경우의 수 = 1 (아무 동전도 사용하지 않음)
        mem[0] = 1;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                // mem[j] = j원을 만드는 경우의 수
                // j - coins[i] = j원에서 i 번째 동전 1개를 뺏을 때 가치(j -coins[i]원)를 만든 경우의 수
                if (j - coins[i] > -1) {
                    mem[j] += mem[j - coins[i]];
                }
            }
        }

        bw.write(mem[k] + "\n");
        bw.flush();bw.close();
    }
}

마무리

DP의 경우도, 필수적으로 익혀야하는 알고리즘 종류 중 하나입니다. 거의 대부분의 입사 코딩테스트에서 꼭 나오는 것 같고, 잘 익혀두시면 도움이 될 수 있습니다. 혹시 궁금하신 점이나 이상한 점이 있다면 댓글 부탁드리겠습니다.

감사합니다.

#능력 회복하기,
#동전1,
#백준,
#백준 2293,
#알고리즘

글이 도움이 되셨다면, 커피 한 잔만 사주세요!

Comments

Copied to clipboard

[BOJ/백준] 동전1 (DP)

Table of Contents

백준 2293: 동전1

풀이

정답 코드 (DP)

마무리