(JAVA) 백준 문제 풀이 - 동적계획법 단계 - 9095번 1,2,3 더하기 (실버 3)

최근 동적계획법 문제가 약한것 같아 다시 해당 단계를 풀어보는 중이다. 이번 문제는 정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하는 문제이다. 점화식을 만드는데 꽤 애를 먹었는데 어떻게 풀었는지 정리해보고자 한다.

---

점화식이 가장 중요하다.

이번 문제에서의 핵심은 점화식을 어떻게 만드느냐였다. 처음에 점화식을 어떻게 만들지를 생각하지 못해서 꽤 애를 먹었는데 결국 핵심은 어떤 정수를 1,2,3의 합으로 나타내는 방법이므로 만드는 숫자는 3개로 한정된 것이 핵심이였다.

우선, 초기값으로 1,2,3에 해당하는 값인 1,2,4를 dp배열에 넣어두었다. 그 후, 4 이상의 값은 n-3,n-2,n-1을 모두 더한값과 같게된다.

무슨 말인지 잘 이해가 안되니 4와 5를 예로 들어보자.

만들 숫자가 1,2,3이므로, 4는 다음의 경우의 수를 가진다.

1. 1일 경우 3을 더하면 만들어진다.
2. 2일 경우 2를 더하면 만들어진다.
3. 3일 경우 1을 더하면 만들어진다.

위 케이스를 각각 dp배열로 생각해 보았을때, 결국 dp[3] + dp[2] + dp[1]이 되는 것을 알 수 있다.

쉽게 말해 주어진 값 4를 -1, -2, -3한 값과 같은 것이다.

그렇다면 5는 어떻게 되는가?

1. 1일 경우 4를 더하면 만들어진다.
2. 2일 경우 3을 더하면 만들어진다.
3. 3일 경우 2를 더하면 만들어진다.

즉, dp[4] + dp[3] + dp[2]의 값과 같다.

4의 값은 아까 설명했듯 dp[3] + dp[2] + dp[1]의 값과 같으므로 우리는 동적 계획법을 통하여 문제를 풀 수 있게 되는 것이다.

그럼 위의 로직을 코드로 구현해보자.

---

import java.io.*;
import java.util.*;

class Main{
    public static int n,m;
    public static Integer[] arr;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new Integer[12];
        arr[1] = 1;
        arr[2] = 2;
        arr[3] = 4;

        for (int i = 0; i < n; i++) {
            m = Integer.parseInt(br.readLine());
            System.out.println(cal(m));
        }

    }

    public static int cal(int a) {
        if (arr[a] != null) {
            return arr[a];
        }

        arr[a] = cal(a - 1) + cal(a - 2) + cal(a - 3);
        return arr[a];
    }
}

나는 Top-Down 방식으로 로직을 구현하였는데 dp배열 arr을 선언하고 1,2,3의 인덱스에 초기값을 넣어두었다.

그리고 계산할 숫자 m을 입력받아 cal 메소드를 통하여 계산을 한다.

해당 메소드는 arr배열에 해당 인덱스의 값이 없으면 -1,-2,-3 한 값을 모두 더하여 리턴한다.

 

이렇게 간단히 동적계획법을 이용하여 로직을 구성 할 수 있었다.

점화식을 만드는 건 아직 연습이 많이 필요한 것 같다..