[DP] 백준 - 파도반 수열

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

9461번: 파도반 수열

 

-문제해설

기본적인 다이나믹 프로그래밍 문제이다. 바텀업방식으로 풀면 금방 풀 수 있다.

이때 dp 배열은 long타입으로 선언해야된다.

 

점화식은 다음과 같다.

dp[n] = dp[n-3] + dp[n-2] (단, n이 1 또는 2일 때는 dp[1] = 1, dp[2] = 1 )

 

 

-자바

package ex;

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


public class BJ9461 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt( br.readLine() );
		
		long[] dp;
		while( t --> 0 ) {
			 int n = Integer.parseInt( br.readLine() );
			 dp = new long[n+1];
			 
			 if( n == 1 ) dp[1] = 1; 
			 else if( n == 2 ) {
				 dp[1] = 1;
				 dp[2] = 1;
			 } else {
				 dp[1] = 1;
				 dp[2] = 1;
				 for( int i=3; i<=n; i++ ) dp[i] = dp[i-3] + dp[i-2];				
			 }
			 
			 System.out.println( dp[n] );
		}
	}
}

 

 

-파이썬

t = int( input() )
for _ in range( t ):
    n = int( input() )
    
    dp = [0] * 101
    if n == 1: dp[1] = 1
    elif n == 2: 
        dp[1] = 1
        dp[2] = 1
    else:
        dp[1] = 1
        dp[2] = 1
        for i in range( 3, n+1 ):
            dp[i] = dp[i-3] + dp[i-2]
    print( dp[n] )