[백준/DP/11727] 2×n 타일링 2

이미지 클릭시, 문제로 이동됩니닷 :)

Sol

import sys 

input = sys.stdin.readline
n = int(input())
dp = [0]*1001
dp[1] = 1
dp[2] = 3

for i in range(3,1001):
  # 전전항 * 2 + 전항
  dp[i] = (dp[i-2]*2) + dp[i-1]

print(dp[n]%10007)

 

첫 시도만에 문제를 푼거 같지만........ 전혀 아니다.

문제를 푸는데 2시간이 넘게 걸렸다.

 

11726 문제랑 비슷해서 쉽게 풀거라고 생각했는데 규칙을 못찾았다.

 

DP 문제는 인접한 항들 사이의 관계로 식을 만들어서 푸는 문제다.

규칙을 찾아야한다.

 

n이 1일때와 2일때는 출력값을 알고있으니

3일때의 출력값을 구해보았다.

 

 

n=3일때

 

규칙이 보이질 않는다. 4일때의 출력값을 구해본다.

 

n=4일때

모르겠다..

 

우선은 1~4 까지 맞는 출력값을 찾았다고치고 점화식을 구해본다.

구한 점화식으로 8회차일때 171이 나오면 맞는거다.

 

1회	2회	3회	4회	5회	6회	7회	8회
1	3	5	11				171

 

이때부터 머리를 쥐어짜서 11이 나오는 온갖 식을 만들어보았다.

 

1,3,5,11

 

case 1. 일단 더해본다. 땡!

1->3 : +2

3->5 : +2

5->11 : +6

 

case 2.  전항 + 전전항 + 회차 땡!

3 = 1+2

11 = 5+3+3

 

case 3. 이전에 나온 항 전체 + 2 땡!

3 = 1+2

11 = 1+3+5+2 => 이전에 나온 항 전체 + 2

 

case 4. 이전항 * 2 + 1 땡!

3 = 1*2+1

11 = 5*2+1

..........

 

171이 안나온다....... 어떻게 나오는거냐....

도저히 모르겠어서 이때부터 n=5일때 출력 값을 구해보았다.

그리고 지우고 그리고를 반복하다..

현타가온다.

 

내일 출근해야하니 식 부분을 찾아보았다...

(참고로 n=5 일때 출력값은 21이었다. 17개까진 찾았었는데;;)

 

진짜 이런거 다른 분들은 어떻게 규칙을 찾는걸까....

그래도 문제를 풀다보면 나아질거라고 생각한다..... (그러겠지..?)