백준 15990번 - 1, 2, 3 더하기 5 (Java 8)

https://www.acmicpc.net/problem/15990

15990번: 1, 2, 3 더하기 5

코드 :

1. dp, 바텀업

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

public class Main {
    public static final int MOD = 1_000_000_009;
    static long[][] nums;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        //init
        nums = new long[100_001][4];
        nums[1][1] = 1;
        nums[2][2] = 1;
        nums[3][1] = 1;  //3을 나타내는 방법 중 마지막이 +1인 경우의 수
        nums[3][2] = 1;  //3을 나타내는 방법 중 마지막이 +2인 경우의 수
        nums[3][3] = 1;  //3을 나타내는 방법 중 마지막이 +3인 경우의 수

        //4부터 n까지 채우기
        for (int i = 4; i < 100_001; i++) {
            nums[i][1] = (nums[i - 1][2] + nums[i - 1][3]) % MOD;
            nums[i][2] = (nums[i - 2][1] + nums[i - 2][3]) % MOD;
            nums[i][3] = (nums[i - 3][1] + nums[i - 3][2]) % MOD;

        }

        for (int i = 0; i < T; i++) {
            int n = Integer.parseInt(br.readLine());
            long result = (nums[n][1] + nums[n][2] + nums[n][3]) % MOD;
            sb.append(result).append("\n");
        }
        System.out.print(sb);
    }
}

long으로 제대로 선언하지 않아서 계속 틀렸다. 숫자가 그렇게 커질줄은 몰랐다. 그 외에도 괄호를 제대로 하지 않는 등 실수가 많았다.

 

또, 규칙을 찾는게 너무 어렵다. dp를 쓰라고 명시되어있음에도 불구하고, 점화식을 못만드는게 문제다.

 

 

참고 :

팡트루야님 블로그

다듬다보니 코드가 아예 같아졌다.