백준 23256 자바 - 성인 게임 (BOJ 23256 JAVA)

문제 : https://www.acmicpc.net/problem/23256

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/23200/BOJ_23256.java

 

  규칙성을 찾기가 난해했다. 일단 결과부터 말하자면 이 문제는 점화식 2개를 만들어 풀어야 한다. 전체 경우의 수를 따로 세고, 전체의 경우 중 맨 우측이 1칸짜리 블록인 경우를 따로 세야 한다. 예를들어 N=1인 경우 전체 경우의 수는 7이고, 맨 우측이 1칸짜리 블록인 경우 3가지로 다음과 같다. 그럼 왜 그렇게 해야하는지 풀이를 써보겠다.

 

 

1. N=2 이상일 경우 이전 경우에서 우측에 3개가 추가된다. 이 때 그 3개는 다음의 3가지 경우가 있다.

따라서 일단 f(n)이 n일 때의 경우의 수라 하면, f(n) = f(n-1) * 3 은 쉽게 알 수 있다.

 

 

 

2. 다음으로 우측이 1칸짜리 블록인 경우에는 2칸짜리 블록을 중간에 놓아 추가로 만들 수 있는 모양이 있다. N=1일 때의 예시 이미지 중 첫번째 이미지에서 만들어진 모양은 다음과 같다.

그럼 g(n)이 n일 때 가장 우측이 1칸짜리 블록인 경우의 수라 하면, f(n) = f(n-1) * 3 + g(n-1) * 4 가 됨을 알 수 있다.

 

 

3. 그럼 이제 g(n)에 대한 점화식을 구해야 한다. 일단 '1'의 과정을 통해 구해진 3가지 경우 중

위의 모양이 더해진 경우만 가장 우측이 1칸짜리 블록이 된다. 따라서 일단 g(n) = f(n-1) 이 된다.

 

 

4. 그리고 '2'의 과정을 통해 나온 4가지 경우 중 2가지 경우도 우측이 1칸짜리 블록이 된다.

따라서 g(n) = f(n-1) + g(n-1) * 2 가 된다.

 

 

 

최종적으로 f(n)과  g(n) 점화식은 다음과 같다.

f(n) = f(n-1) * 3 + g(n-1) * 4

g(n) = f(n-1) + g(n-1) * 2

그럼 이 2가지를 DP로 계산하면 된다. 코드에서는 f(n)의 역할이 dp[0][n]이고, g(n)의 역할이 dp[1][n] 이다.