[Python][백준 2133][DP] 타일 채우기 - 컴도리돌이

반응형

---

풀이과정

해당 문제는 뭔가 일단 규칙성을 찾아야 하게끔 생겨 버렸다.

😶‍🌫️😶‍🌫️

 

일단 n이 홀수이면 0인 거 알겠지만,

 

n이 짝수일 때 규칙성을 찾는데 애를 먹었다.

 

일단 n이 2일 때는 3이다.

 

그다음 n이 4일 때는 11이다.

근데 여기서 n이 2일 때 경우의 수 각각 2,2이기 때문에

2 * 2에 새로운 모양 2개를 더해준 값이다.

 

그렇다면 일단 dp [2] * dp [2] + 2라고 표현할 수 있다.

 

그다음 n이 6일 때는 41이다.

dp [4] * dp [2] + dp [2] * 2 + 2

 

그다음 n이 8일 때는 

dp [6] * dp [2] + (dp [4] + dp [2] ) * 2 + 2

 

그다음 n이 10일 때는 

dp [8] * dp [2] + (dp [6] + dp [4] + dp [2]) * + 2

 

n일 경우에는

dp [n-2] * dp [2] + (dp [n-4] +... + 1 ) * 2

라는 점화식이 나온다.

 

물론 이 과정까지 그림을 그리면서 나올 수 있는 점화식이었다.

 

😔

너무 힘들고 힘들었따...

---

풀이 코드

n =  int(input())
if not n % 2:
  dp = [1,0,3,0,11] + [0] * (n+1)
  if n == [0,2,4] : print(dp[n])
  else :
    for i in range(6,n+1,2) :
      for j in range(0,i-2,2) :
        dp[i] += dp[j] * 2
      dp[i] += dp[i-2] * dp[2]
    print(dp[n])
else :
  print(0)