2023년 11월 28일 알고리즘 문제풀이
문제
난이도
Lv.2
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def solution(n):
dp = [0 for _ in range(5001)]
dp[2] = 3
dp[4] = 11
for i in range(1,n+1):
if n%2:
return 0
if i%2:
continue
else:
if not dp[i]:
tmp = 2
tmp += dp[i-2]*dp[2]
for x in range(2,i//2):
tmp += dp[i-2*x]*2
dp[i] = tmp%1000000007
return dp[n]
진짜 어렵다. 홀수는 나올수 없으므로 무조건 0이라는 것은 일찍 발견했다. 하지만 일반항을 위한 점화식을 구하기가 어려웠다. 처음에 한 추론은 다음과 같다.
1차 추론 : 이전 짝수 항의 제곱에 2를 더한 값 2차 추론 : 이전 짝수 항과 3의 곱에 2를 더한 값(3은 가로가 2일 때 갯수)
이 후 꽤 많은 경우의수를 더해야 겠다고 생각했다. 점화식을 세우는데 방해가 되는 규칙이 하나 존재했다. 이전 짝수 항들의 조합으로 만들어 낼 수 없는 새로운 형태가 매번 2개 씩 나타난다는 것이다.
따라서 나는 블록을 2가지 종류로 분류했다. 이전 항들의 조합으로 만들 수 있는 것과 그렇지 않은것. 여기서 그렇지 않은 것은 항상 2개였다. 이전 항들의 조합으로 만들 수 있는 것은 전체 길이를 세세하게 나눌 필요가 없었다.
가로의 길이가 10이라고 생각해보자.그리고 모든 경우에 이전 항들의 조합으로 만들어 지지 않는, 새로운 모양이 존재하지 않는다고 가정하자. n(x)는 가로의 길이가 x일 때 만들 수 있는 경우의 수를 의미한다. n(2)xn(8), n(4)xn(6), n(6)xn(4), n(8)xn(2) 로 나눌 필요가 없다. 결론적으로 봤을때 모두 겹치기 떄문이다. n(2)와 n(8)의 조합으로 만들던, n(4)와 n(6)의 조합으로 만들던 간에 결과적으로 합쳤을 때 같다면 따로 계산하는 것은 무의미하다. 따라서 이전항들의 조합으로 만들어질 수 있는 경우는 n(2)와 n(8)의 조합 만 계산하면 된다. 따라서 이전 짝수 항과 n(2)의 곱이 된다.
논리의 과정을 편하게 만들기 위해 새로운 모양이 존재하지 않는다고 가정했지만 이 또한 계산에 포함해야 된다. 다행히 가로의 길이가 4 이상인 경우마다 2개씩 밖에 존재하지 않는다. n(8)도 이전 짝수 항의 조합으로 만들 수 있는 경우와 새로 만들어진 경우 2개가 합쳐진 결과일 것이다. n(8)의 경우 중 이전 짝수 항의 조합으로 만들 수 있는 경우와 n(2)의 조합은 위에 계산에 포함된 결과이다. 포함되지 않은 결과는 새롭게 만들어진 경우인 2가지 뿐이다. 따라서 n(2)와n(8)의 조합은 n(2)2 가 된다. n(4)n(6)도 같은 논리로 n(4) x 2 가 된다. 따라서 n(2)x2 + n(4)x2 + … + n(8)x2 를 알아낼 수 있다.
마지막으로, 아예 새롭게 생긴 경우 2가지를 더해주면 된다.
따라서 n(10) = n(8)xn(2) + {n(2)x2 + n(4)x2 + n(6)*2 + n(8)*2} + 2 이다.
