[백준] 2193 이친수 - DP JAVA

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

2193번: 이친수

코드설명

DP 문제입니다.

 

N=90이기에 90 자리수가 나오면 당연히 int형으로는 처리가 불가능합니다.

long 형 자료형을 사용합니다.

 

문제로직입니다.

DP[101][2] : N번째 자리에서 끝자리가 0으로 끝나는 이친수. N번쨰 자리수에서 끝자리가 1으로 끝나는 이친수 이렇게 생각하여 진행했습니다.

 

다른 풀이로는,

DP[N] = DP[N-1] + DP[N-2]라는 점화식을 찾아내어 적용시키면 됩니다.

위의 점화식을 생각해보면,

N번쨰 자리에 0 이 올때는 N-1의 숫자에는 무조건 마지막으로 0 을 붙여서 DP[N-1]을 그대로 가져옵니다.

N번쨰 자리에 1 이 올때는 N-1의 자리에 무조건 0 이 와야합니다. DP[N-2] 에다가 무조건 0을 붙이는 경우에다가 추가로 N번째 자리에는 1을 붙이도록 합니다.

DP[N] = DP[N-1] + DP[N-2] 가 됩니다.

 

첫번쨰 풀이는 떠올렸지만, 두번쨰 풀이는 떠오르지 않았는데, 해당 풀이방법도 좋은 접근인것 같습니다.

 

코드

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

public class Main {
	
	public static int N;
	public static long[][] dp;
	public static int answer;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	dp = new long[101][2];
    	dp[0][0] = 0; //0자리수
    	dp[0][1] = 0; //0자리수
    	
    	dp[1][0] = 0;  //1. 이친수는 0으로 시작하지 않으므로 0 개입니다.
    	dp[1][1] = 1; //2.이친수에서는 1이 두번 연속으로 나타나지 않습니다. 즉, 11을 부분 문자열로 갖습니다.
    	
    	dp[2][0] = 1;
    	dp[2][1] = 0;
    	
    	for(int i=3; i<=N;i++) {
    		dp[i][0] = dp[i-1][1] +  dp[i-1][0];
    		dp[i][1] = dp[i-1][0];
    	}
    	System.out.println(dp[N][0] + dp[N][1]);
    	
    	
    }
}