[DP] 백준 - 1,2,3 더하기 5

-자바

 

와 계속 시간초과나서 헤맸다;

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

public class Main {
	private static BufferedWriter bw = 
			new BufferedWriter( new OutputStreamWriter(System.out));
	private static int t, n, div, limit, sum;
	private static int[][] d;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		div = 1_000_000_009;
		limit = 100_000;
		d = new int[100_001][4];
		d[1][1] = d[2][2] = d[3][1] = d[3][2] = d[3][3] = 1;
		
		for( int j=4; j<=limit; j++ ) {
			for( int k=1; k<=3; k++ ) {
				if( k==1 ) d[j][k] = ( d[j-1][2] + d[j-1][3] )% div;
				else if( k==2 ) d[j][k] = ( d[j-2][1] + d[j-2][3] )% div;
				else if( k==3 ) d[j][k] = ( d[j-3][1] + d[j-3][2] )% div;
				d[j][k] %= div;
			}
		}	
		
		t = Integer.parseInt( br.readLine() );
		
		for( int i=0; i<t; i++ ) {
			n = Integer.parseInt( br.readLine() );
			sum = 0;
			
			for( int j=1; j<=3; j++ ) {
				sum += d[n][j];
				sum %= div;
			}
			bw.write( sum + "\n" );
			bw.flush();
		}
		
		bw.close();
		br.close();
	}
}

 

-파이썬

t = int(input())

div = 1000000009
limit = 100000

d = [ [0] * 4 for i in range( limit+1 ) ]
d[1][1] = 1
d[2][2] = 1
d[3][1] = 1
d[3][2] = 1
d[3][3] = 1

for i in range( 4, limit+1 ):
    for j in range( 1, 4 ):
        if j==1: d[i][j] = ( d[i-1][2] + d[i-1][3] ) % div
        elif j==2: d[i][j] = ( d[i-2][1] + d[i-2][3] ) % div
        elif j==3: d[i][j] = ( d[i-3][1] + d[i-3][2] ) % div
        d[i][j] %= div


for i in range(0,t):
    n = int(input())
    sum = 0
    
    for j in range( 1, 4 ):
        sum += d[n][j]
        sum %= div
    
    print( sum )