백준 2193 이친수

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

2193번: 이친수

2차원 다이나믹 배열 이용(변수 두개 사용)

D[ N ][ L ] = D [ 자리수 ] [ 마지막수 ]라 했을 때,

 

경우의 수를 나누어서 생각해보자.

1) 마지막 자리에 0이 오는 경우 => D[ N ][ 0 ] = D[ N - 1 ][ 0 ] + D[ N - 1 ][ 1 ]

2) 마지막 자리에 1이 오는 경우 => D[ N ][ 1 ] = D[ N - 1 ][ 0 ]

두가지 경우의 수가 있다.

 

그럼 초기값을 어떻게 설정하면 좋을까?

길이가 가장 짧은 이친수는 길이가 1이라고 할 수 있다. 0 또는 1

1) D[ 1 ][ 0 ] = 0 => 문제에서 이친수는 0으로 시작하지 않는다는 조건이 있기때문에 초기값은 0에 해당한다.

2) D[ 1 ][ 1 ] =  1

 

1차원 다이나믹 배열 이용(변수 하나 사용)

해당 문제는 0 과 1만 사용하기 때문에 1차원 다이나믹 배열을 이용 할 수 있다.

D[ N ] = N 자리 이친수 라고 해보자.

 

1) N 자리 이친수가 마지막이 0 인경우 => N - 1 자리수에 올 수 있는 수는 0 또는 1 이다.

즉, D[ N - 1] 자리의 이친수를 만들고 0을 붙이면 되기때문에 D [ N ] = D[ N - 1] 이 된다.

 

2) N 자리 이친수가 마지막이 1 인경우 => N - 1 자리수에 올 수 있는 수는 0 이다.

즉, D[ N - 1] 에는 무조건 0이오고 D[ N - 2] 에는 0 또는 1이 올 수 있기때문에 D [ N ] = D[ N - 2] 이 된다.

 

1차원 다이나믹 배열을 이용하여 풀이한 코드

import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[] d = new long[n+2];
		d[1] = 1; //1자리 이친수는 1만 가능 (이친수는 0으로 시작하지 않는다는 문제 조건)
		d[2] = 1; //2자리 이친수는 10만 가능 (이친수는 0으로 시작하지 않고, 11이 연속되지 않는다는 문제 조건)
		
		for(int i = 3; i <= n; i++) {
			d[i] = d[i-1] + d[i-2];
		}
		System.out.println(d[n]);
	}
}