[백준] 9095: 1, 2, 3 더하기 JAVA

접근

이번주 스터디에서는 알고리즘을 정한 후 문제를 골랐기 때문에 DP로 접근해야 한다는 사실을 알고 풀었지만, 모르고 문제를 푼다면 내 나름의 판단 근거는 실행 시간이다. 뭔가 복잡해보이는데 제한 시간이 1초 이내로 짧다면 DP일 가능성이 높다고 생각한다. 

 

각설하고 문제로 돌아가면, 사용되는 숫자가 1~3로 3가지밖에 없어서 10, 50, 100원으로 나누던 동전 문제와 유사하다는 느낌을 받았다. n의 최댓값이 10으로 매우 작으므로 숫자 2부터 하나씩 계산하면 될 것 같다. 사용 가능한 최대 숫자가 3이기 때문에 3번마다 규칙이 보이길 바라면서 개수를 세어봤다. 그런데 나는 합을 나타낼 때 수를 '1개' 이상 사용해야 한다는 조건을 제대로 읽지 못해서 시간을 많이 낭비했다..ㅎㅎ 무조건 합(+)이 들어가야 한다고 생각했는데 역시 문제를 잘 읽자.. 

 

n = 1) 1가지

1

n = 2) 2가지

2 / 1+1

n = 3) 4가지

3 / 2+1, 1+2

n = 4) 7가지

3+1, 1+3, 2+2 / 2+1+1, 1+2+1, 1+1+2 / 1+1+1+1

 

숫자 n에 따른 경우의 수를 저장하는 배열을 dp[]라고 할 때, 위 규칙을 보면 dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 식을 유추해볼 수 있다. 이 방법대로 코드를 구현하자. 참고로 dp[5] = 13, dp[6] = 24... 으로 성립하는걸 알 수 있다. 이렇게 되는 이유는,

4 = 1 + 3 (3을 만들 수 있는 경우의 수)

   = 2 + 2 (2를 만들 수 있는 경우의 수)

   = 3 + 1 (1을 만들 수 있는 경우의 수)

가 되기 때문

 

코드

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

public class Main {
    static int MAX_VALUE = 11;

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

        // n이 작으므로 매번 동일한 연산을 하지 않도록 미리 수행했음
        int[] dp = new int[MAX_VALUE];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        for(int i = 4;i < MAX_VALUE;i++)
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];

        // 테스트케이스별 결과 출력
        int tc = Integer.parseInt(br.readLine());
        for(int t = 0; t < tc; t++){
            int n = Integer.parseInt(br.readLine());
            sb.append(dp[n]).append("\n");
        }

        System.out.println(sb);
    }
}