[DP] 백준 - 피보나치 함수

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

1003번: 피보나치 함수

 

-문제해설

DP의 기본적인 문제인 것 같다. 단순히 피보나치 값을 구하는 것이 아니라 특정 피보나치 수의 1의 개수와 0의 개수를 구하는 문제이다.

 

2차원배열을 선언해서 0번 인덱스에는 0의 개수, 1번 인덱스에는 1의 개수를 집어넣고

dp[i][0] = dp[i-1][0] + dp[i-2][0]

dp[i][1] = dp[i-1][1] + dp[i-2][1]

점화식을 통해 n행의 배열값을 출력하면 정답이다.

 

 

-자바

package dp;

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

public class BJ1003 {

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

 

-파이썬

t = int( input() )
dp = [ [0]*2 for _ in range( 41 ) ]
dp[0][0] = 1; dp[1][1] = 1
for i in range( 2, 41 ):
    dp[i][0] = dp[i-1][0] + dp[i-2][0]
    dp[i][1] = dp[i-1][1] + dp[i-2][1]
for _ in range( t ):
    n = int( input() )
    print( dp[n][0], dp[n][1] )