[백준 - 자바] 2193번: 이친수

 

---

문제를 요약하면 다음과 같다.

이진수 중 다음 성질을 만족하는 수를 이천수라고 한다.

1. 0으로 시작하지 않는다.

2. 1이 두번연속으로 나타나지 않는다.

 

숫자의 길이 N이 주어졌을 때, N자리 이천수의 개수를 구하시오.

 

 

설계

Dynamic Programming (동적계획법) 문제를 설계할 땐, 인접한 Computation Level 간의 "어떠한 재귀식"이 성립하는가? 를 파악하는 것이 전부이다. 다시 말해, Recursive Property를 Establish 해야한다.

 

Recursive Property Establish

이를 위해선 계산단계를 어떻게 구분할 것인지 생각해봐야하고, 이에 따라 바로 풀리는 수준의 문제단계 (Lowest Level)에 대해서도 생각해봐야 한다. 즉, 아래와 같이 계산단계를 분리할 수 있을 것이다.

( N자리 이천수의 개수는 바로 알 수 없지만, 1자리 이천수의 개수는 바로 알 수 있다. ( " 1 " ) --> 1개 )

목표 (Top-most Level) :  N자리 이천수의 개수  ... Lowest Level :  1자리 이친수의 개수

=>

Lowest Level (1자리 이친수의 개수)	( "1" ) -> 1개
+1 Level (2자리 이친수의 개수)	( "10" ) -> 1개
+2 Level (3자리 이친수의 개수)	( "101", "100" ) -> 2개
+3 Level (4자리 이친수의 개수)	( "1010", "1000", "1001" ) -> 3개
... Top-most Level (N자리 이친수의 개수)

 

 

DP [ digit (자릿수) ] [ val (자릿수의 값) ] = "이친수의 개수" 라고 정의하자.

ex.

DP[3][0] 의미: 셋째자리가 0인 이친수의 개수

DP[4][1] 의미: 넷째자리가 1인 이친수의 개수

 

위의 표를보면,

넷째자리가 0인 이친수 ( "1010", "1000" )의 개수 =  셋째자리가 1인 이친수 개수 + 0인 이친수 개수

넷째자리가 1인 이친수 ( "1001" )의 개수 = 셋째자리가 0인 이친수의 개수

 

위에서 정의한 DP로 표현하면

DP [4][0] = DP[3][0] + DP[1][0]

DP [4][1] = DP[3][0]

 

일반화하면, 다음과 같은 재귀식을 구할 수 있다.

Recursive Property

case 1)  if ( val == 0 )

DP [digit] [val] = DP [digit-1] [0] + DP [digit-1] [1] ;

 

case 2) if ( val == 1)

DP [digit] [val] = DP [digit-1] [0] ;

 

 

 

 

구현

1. DP 방식으로 구현 (Bottom-Up)

2. Top-Down 방식으로 구현

3. Top-Down  +  Memoization 방식으로 구현

 

 

1. Dp 방식으로 구현

public static void main(String[] args) throws NumberFormatException, IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int N = Integer.parseInt(br.readLine());
	
	long[][] DP = new long[N+1][2];
	DP[1][0] = 0;
	DP[1][1] = 1;
	
	for (int digit=2; digit<N+1; digit++) {
		for (int val=0; val<2; val++) {
			if (val == 0) 
				DP[digit][val] = DP[digit-1][0] + DP[digit-1][1];
			if (val == 1)
				DP[digit][val] = DP[digit-1][0];
		}
	}
	System.out.println(DP[N][0] + DP[N][1]);
	
}

 

 

2. Top-Down 방식으로 구현

 

static long result = 0;
static int N;

public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	N = Integer.parseInt(br.readLine());
	
	for (int val=0; val<2; val++) {
		result += recur(N, val); // 순수 Top-Down Ver
	}
	System.out.println(result);
	
}


public static long recur(int digit, int val) {
	/*base case
	 * 재귀호출이 언제 종료? (파라미터가 향해가고있는 dead end를 파악)*/
	if (digit == 1 && val == 0) return 0;
	if (digit == 1 && val == 1) return 1;
	
	/*recursive case*/
	if (val == 0) {
		return recur(digit-1, 0) + recur(digit-1, 1);
	}
	else {
		return recur(digit-1, 0);
	}
}

 

문제점: 계산중복으로 인한 시간초과

 

 

3. Top-Down 개선 (Memoization)

static long result = 0;
static int N;
static Long[][] DP;

public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	N = Integer.parseInt(br.readLine());
	
	DP = new Long[N+1][2];
	DP[1][0] = 0L;
	DP[1][1] = 1L;
	for (int val=0; val<2; val++) {
		result += recur_memoization(N, val); // Top-Down + Memoization
	}
	System.out.println(result);
	
}

public static Long recur_memoization(int digit, int val) {
	/*base case*/
	if (digit == 1) return DP[digit][val];
	
	/*recursive case*/
	if (DP[digit][val] == null) {
		if (val == 0) {
			DP[digit][val] = recur_memoization(digit-1, 0) + recur_memoization(digit-1, 1);
		}
		else {
			DP[digit][val] = recur_memoization(digit-1, 0);
		}
	}
	return DP[digit][val];
}

Memoization으로 계산중복 방지

( if (Dp[digit][val] == null )