https://www.acmicpc.net/problem/2133
1차 구현
처음에는 아래와 같은 모양을 기준으로 생각했습니다.
(아래의 모양을 $이라고 칭하겠습니다.)
또한, 홀수의 케이스가 주어질 때는 항상 0을 나타냄을 알 수 있으므로 짝수일 경우만 생각해주었습니다.
import sys
input = sys.stdin.readline
size = int(input())
if size % 2 != 0:
print(0)
elif size == 2:
print(3)
else:
result = 0
result += (3 ** (size / 2))
result += (3**((size/2) - 1)) * 2
print(int(result))결과는 틀렸습니다.😫
2차 구현
고민과 수많은 삽질.. 끝에 드디어 2차 구현을 완료하였고, 다행히 통과했습니다.😚
그럼 통과할 때, 생각했던 아이디어에 대해서 말씀드리겠습니다.
미숙하더라도 한 명의 생각이라고 생각하시고 참고해주세요 ^^
먼저, DP 범주에 들어가는 문제로, 이를 해결하는 가장 대표적인 점화식을 세우는데에 집중해보았습니다.
2일 때에 3은 자명하므로 4일 때부터 짝수를 기준으로 경우를 생각해보았습니다.
먼저, 가능 시나리오를 나누어보면
1. 이전 짝수의 경우에서 두 칸이 추가된 경우
2. 1X2 타일 두개가 속해서 2칸을 차지하는 경우
3. 가운데에 큰 덩어리가 생겨서 경우를 막는 경우
시나리오 1
이전 짝수일 때의 전체 경우의 수에 3을 곱해주면 됩니다.
시나리오 2
1X2 타일이 2칸을 차지하는 경우에서는 차지하는 크기를 증가시켜서 과거의 경우의 수를 가져와서 X2를 해주면 됩니다.
시나리오 3
시나리오 3은 시나리오 2와 동일하게 처리되는 경우도 있는데, 주어지는 입력이 2보다 크면 언제나 존재합니다. 해당 시나리오는 무조건 2가지 경우의 수가 나옵니다.
따라서 모든 시나리오를 다 더하면 해당하는 경우의 수가 나옵니다.
이를 간단하게 나타내면 아래와 같습니다.
이를 바탕으로 코드를 구성하면 아래와 같습니다.
import sys
input = sys.stdin.readline
size = int(input())
count = [0 for i in range(31)] # 배열의 크기는 30까지의 입력을 받을 수 있게 설정
count[2] = 3 # 2일 경우는 케이스를 나누기 보다는 특이 케이스로 처리
if size >= 4: # 4일 때부터 반복문 시작
for i in range(4,size+1):
if i % 2 == 0: # 짝수일 경우만 점화식 적용
multi = 2
for j in range(i):
if j % 2 == 0 and j != 0:
if j == (i-2):
multi = 3 # 바로 이전 짝수의 값은 X3을 해주어야 하므로 이를 처리
count[i] += count[j] * multi
multi = 2
count[i] +=2 # 마지막 시나리오를 처리
print(count[size]) # 결과 출력