백준(Backjoon) 9625, BABBA

문제풀이

위 문제는 다이나이믹 프로그래밍 문제이다. N의 수에 따른 A와 B의 개수를 계산하면 아래와 같다.

N	A	B
1	0	1
2	1	1
3	1	2
4	2	3
5	3	5
6	5	8

A와 B의 수의 변화는 피보나치 수를 따르고 있다. 단, 차이점은 A는 N==1일때 0이고 B는 N==1일때 1인점이 차이가 있다. 따라서 위 문제를 해결하기 위해서 재귀 함수를 구현하였고 메모제이션 기법을 적용하였다. 단, 메소드의 인자에 변수를 하나 추가하였다. 이 변수는  N==1일때 값을 정하는 변수(0,1)이다.

 

소스코드

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


public class Main {
	static int[] dp;
	
	public static int solution(int n, int initVal)
	{
		if(n==1)
		{
			return initVal;
		}
		if(n==2)
		{
			return 1;
		}
		
		if(dp[n]!=0)
		{
			return dp[n];
		}
		else
		{
			dp[n] = solution(n-1, initVal) + solution(n-2, initVal);
			return dp[n];
		}
	}
		
	public static void main(String args[]) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		dp = new int[1000001];
		int A = solution(n, 0);
		dp = new int[1000001];
		int B = solution(n, 1);
		
		System.out.println(A + " " + B);
	}
}