[백준] 15988 : 1, 2, 3 더하기 3 (JAVA)

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

 

[풀이과정]

모듈러 연산의 분배법칙

: 처음부터 끝까지 모두 더하고 % 연산을 하기 == 더하는 중간중간 % 연산을 하기
즉, (A+B+C...) % n == ((A%10) + (B%10) + (C%10) + ...) % n

 

N이 3미만 일 때 고려

DP[1], DP[2], DP[3]는 직접 초기화하기 때문에 값이 3보다 작으면 런타임에러 발생

 

[코드]

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

/*
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성
 */
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static int N;
    static long[] DP;
    static final int INF = 1_000_000_009;
    public static void main(String[] args) throws IOException {
        int T = Integer.parseInt(br.readLine());
        for(int t = 0; t < T; t++){
            init();
            if(N > 3) {
                getDP();
                sb.append(DP[N]).append('\n');
            }
            else{
                switch(N) {
                    case 1:
                        sb.append(1).append('\n');
                        break;
                    case 2:
                        sb.append(2).append('\n');
                        break;
                    case 3:
                        sb.append(4).append('\n');
                        break;
                }

            }
        }
        /*
        [출력]
        각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력
         */
        System.out.println(sb);
    }

    static void init() throws IOException {
        /*
        [입력]
        1. 테스트케이스 개수 T
        2. N (1 <= N <= 1_000_000)
         */
        N = Integer.parseInt(br.readLine());
        DP = new long[N+1];
    }

    static void getDP(){
        DP[1] = 1;
        DP[2] = 2;
        DP[3] = 4;

        for(int n = 4; n <= N; n++){
            DP[n] = (DP[n-3] + DP[n-2] + DP[n-1]) % INF;
        }
    }
}