문제
먼저 이문제를 봤을 때 예제 출력만봐도 int형의 최댓값을 가볍게 넘어감을 알 수 있다.
그에 따라 시간복잡도를 줄여줘야하고 당연히 이에따라 모든 경우를 세어주는 부르트포스 알고리즘을 사용하는 방식은 아닌 것을 알 수 있다. 그 다음으로 시간복잡도를 줄일 수 있는방법은 이진탐색 다이나믹 프로그래밍 등이 있지만 딱 봤을 때 dp를 적용해 볼 수 있을 것이다.
그렇다면 dp가 적용될려면 이전 결과와 다음결와 즉 d[i]와 d[i-n]과의 연관성을 찾아낼 수 있어야 한다.
여기서의 d[i]는 가로로 긴 2 x n 직사각형의 i길이까지 주어진 타일2개로 채울 수 있는 경우의 수를 나타낸 것이고
d[i]의 연관성여부를 따져보겠다.
먼저 d[i]와 d[i-1]의 관계는 d[i-1]의 경우의 수에서 i번째 줄만 채워주면 되므로
d[i]에는 d[i-1]의 경우의수에서 2 x 1의 타일만 채워주면 되므로 d[i-1]과 d[i]의 관계는
d[i] = (d[i-1] + 또다른 경우의 수) 로 결론을 지을 수 있고
그다음은 d[i]와 d[i-2]와의 관계이다. 이때는 d[i-2]에서 남은두칸을 2 x 1타일 두개로
채워 줄수 있지만 이는 d[i-1]에 2 x 1타일을 채워주는 방식과 겹치므로 고려해주지 않는다.
따라서 d[i]를 만들어 줄 때 d[i-2]경우의 수에서 1 x 2타일을 2개 채우거나 2 x 2타일을 1개 채우는 2가지경우의수가 있으므로
d[i] = (d[i-1] + 2 * d[i-2]) + 또다른 경우의 수 로 결론을 짓는다.
d[i]와 d[i-3]의 관계는 타일이 최대 2만큼의 길이만큼 영향을 끼치므로
고려해볼 필요가 없고 d[i-1]과 d[i-2]만으로 d[i]가 표현가능해지므로
따라서 d[i]의 점화식은 d[i] = d[i-1] + 2 * d[i-2]가 된다.
이를 코드에 녹여보면
#점화식
#걍
#d[i] = d[i-1] + 1 더하기 d[i-2] * 2 = d[i]
d = [0] * 1001
d[0] = 1
d[1] = 1
d[2] = 3
#바텀업 방식으로 d[i] 먼저 구해주기
#(단순더하기라 직접 251번 계산해줘도 무방하다.)
for i in range(3, 251):
d[i] = (d[i-1] + d[i-2] * 2)
while True:
try:
N = int(input())
print(d[N])
except:
break;
try except구문을 이용해서 이 문제의 입출력 방식을 구현해봤다.
