15993 : 1,2,3 더하기 8 - JAVA

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

 

dp 문제이다. 처음에 문제를 읽지 않고 코인 수 구하기와 비슷한 걸로 오해를 했으나, 완벽히 다른 문제임을 깨달았다.

홀수개의 i-1을 사용한 수, i-2를 사용한 수, i-3을 사용한 수에서 숫자 하나를 더하면 짝수가 되고, 짝수개의 i-1,i-2,i-3을 사용한 수에서 숫자 하나를 더하면 홀수가 된다.

 

짝수개와 홀수개를 나눠서 풀었다.

 

소스코드

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

public class Main6 {
    static int mod = 1000000009;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        long[] coin1 = new long[100001];
        long[] coin2 = new long[100001];
        //2는 짝수이기에 없음
        coin2[1] = 1;
        coin1[2] = 1;
        coin2[2] = 1;
        coin1[3] = 2;
        coin2[3] = 2;
        for(int i = 4; i < 100001; i++){
            coin1[i] = (coin2[i-1] + coin2[i-2] + coin2[i-3])%mod;
            coin2[i] = (coin1[i-1] + coin1[i-2] + coin1[i-3])%mod;
        }
        int t = Integer.parseInt(br.readLine());
        while(t-->0){
            int n = Integer.parseInt(br.readLine());
            bw.write(coin2[n]%mod + " " + coin1[n]%mod +'\n');
        }
        bw.flush();
        bw.close();
        br.close();
    }
}