문제
전형적인 DP문제로 좀 어려운 문제이다.
나는 처음에 이 문제를 접했을 때 DP 자체가 너무 약해서 DP를 다시공부하고 풀었다.
그래도 스스로 못풀겠어서 유튜브나 다른 솔루션을 참고해가며 풀었다.
왜 DP문제인가?
1. 큰문제를 작은 문제들로 나눌수 있다.
2. 큰문제에서 분할된 작은문제들은 항상 같은 결과를 가진다.
n개의 타일의 경우의 수에 대해선 n - 1개의 타일의 경우의수로 나눌수있고, n - 2개의 타일의 경우의 수로 나눌수있다.
그리고 각 경우의 수는 항상같다.
그러므로 DP문제이다.
DP문제의 핵심은 규칙성을 찾아 점화식을 도출해 내는 것이다.
나는 문제를 푸는 방법으론 바텀업을 이용해서 반복문과 메모이제이션으로 문제를 풀 것이다.
여기서 메모이제이션이란말은 값을 기억해서 재사용하기 위함인데 DP문제의 조건중 2번내용인 작은 문제들은 항상 같은 결과를 갖기 때문에 작은 문제들에 대한 결과를 메모이제이션해서 불필요하게 다시 계산하지않고 재사용할수 있다.
코드
# DP
# 바텀업으로 풀거임난(반복분 + 메모이제이션)
# 1. 큰문제를 작은문제들로 나눌수있나?
# 2. 작은문제들의 결과는 항상 같나? (큰문제에서 나눈 작은문제들의 결과)
# 메모이제이션을 활용한 DP로 풀수있을듯. 타일문제
N = int(input())
d = [[0 for _ in range(1000001)] for _ in range(2)]
d[0][0] = 0
d[0][1] = 2
d[0][2] = 7
d[1][2] = 1
for i in range(3, N + 1):
d[1][i] = (d[1][i - 1] + d[0][i - 3]) % 1000000007
d[0][i] = (d[0][i - 1] * 2 + d[0][i - 2] * 3 + (d[1][i] * 2)) % 1000000007
print(d[0][N])느낀점
- 이문제 자체를 통해서 DP에 어느정도 다가간것같다. 그래도 어려움..
- 메모이제이션으로 같은 값에 대해선 다시 계산하지않고 재사용함으로써 DP문제를 해결해 나간다는게 무슨의미인지 깨달았다. (DP문제의 조건이 작은 문제들은 항상 같은 결과를 도출이므로!)
