[백준] 9095번: 1,2,3 더하기 - Java,자바

문제접근

이 문제는 예시를 들어준 4를 보면 쉽게 해결할 수 있다.
1을 만들기 위해서 1만 사용하면 된다. [1]
2를 만들기 위해서 1 + 1, 2 가 사용된다. [(1 + 1), (2)]
3을 만들기 위해서는 1 + 1 + 1, 2 + 1, 1 + 2 가 사용되는데 [(1 + 2), (1 + 1 + 1), (2 + 1)]
3을 만들 때를 자세히 보면 1을 만들기 위한 방법 중에 1 만을 사용하는데 여기에 + 2를 통해
1 + 2 = 3 을 만들 수 있다. [1] => [1 + 2]
또한 2를 만들기 위해 사용된 1+1인 2에 + 1을 하게되면 3을 만들 수 있다. [(1 + 1) + 1, (2)+ 1];

따라서, 4를 만들기 위해서는
1. 1 에 + 3 을 해주거나 [1 + 3]
2. 2 에 + 2 를 해주거나 [2 + 2]
3. 3 에 + 1 을 해주면 된다. [3 + 1]
를 통해 아래와 같은 점화식을 얻을 수 있다.
T[N] = T[N - 1] + T[N + 2] + T[N + 3];

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static Integer[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        // 1<= N < 11
//        dp = new Integer[N + 1];
        dp = new Integer[11];

        dp[0] = dp[1] = 1;

        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < N; i++) {
            int number = Integer.parseInt(br.readLine());
            sb.append(recur(number)).append("\n");
        }

        System.out.println(sb);
    }

    private static int recur(int N) {

        if(N == 1) {
            return 1;
        } else if (N == 2) {
            return 2;
        } else if (N == 3) {
            return 4;
        }

        if(dp[N] == null) {
            dp[N] = recur(N - 1) + recur(N - 2) + recur(N - 3);
        }
        return dp[N];
    }
}

코드 상세

• N을 입력받는다. 위의 조건에 자연수 11보다 작다고 하였으니 배열의 크기는 11로 초기화 한다. [N < 11]
  • • 1을 하는 이유는 인덱스는 0부터 시작하는데, 양의 정수를 입력받기 때문이다.

static Integer[] dp;

 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int N = Integer.parseInt(br.readLine());

// 1<= N < 11
//        dp = new Integer[N + 1];
dp = new Integer[11];

• 초기값을 설정한다.

dp[0] = dp[1] = 1;

• 점화식을 이용하여 memoization 배열을 초기화해준다.

private static int recur(int N) {

    if(N == 1) {
        return 1;
    } else if (N == 2) {
        return 2;
    } else if (N == 3) {
        return 4;
    }

    if(dp[N] == null) {
        dp[N] = recur(N - 1) + recur(N - 2) + recur(N - 3);
    }
    return dp[N];
}

• StringBuilder를 만들어 케이스를 입력받아 출력한다.

StringBuilder sb = new StringBuilder();

for(int i = 0; i < N; i++) {
    int number = Integer.parseInt(br.readLine());
    sb.append(recur(number)).append("\n");
}

System.out.println(sb);

정리

이 문제도 N을 만들 수 있는 규칙을 찾는 문제였다. 규칙을 찾을 때는 대부분 예제 출력에서 얻을 수 있는 경우가 대부분이다.
규칙을 찾을때는 최소한의 값을 손으로 써보며 규칙을 찾는것이 좋다. 위에서도 동일하게 4를 가지고 손으로 써가며 규칙을 찾았다.
접근법은 이렇다. 4를 만들기위해서는 조건을 가지고 3가지로 나눌 수 있었다.
1. 3에 1을 더한다. [3 + 1]
2. 2에 2를 더한다. [2 + 2]
3. 1에 3을 더한다. [1 + 3]
이것을 풀어말하자면, dp[1]을 구했던 값에 3을 더하는 수 + dp[2]를 구했던 값에 2를 더하는 경우 + dp[3]에서 + 1을 하는 경우의 수를 더하는 것이었다.

그런데... 모르는 상태에서 다시 풀려면 모르겠는데요...?