💡문제
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×17 직사각형을 채운 한가지 예이다.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
예제입력
8예제출력
171📖내가 작성한 Code
import sys
def two_n_tiling(number):
dp = [1, 3]
if number < 3:
return dp[number - 1]
for num in range(2, number):
dp.append(dp[num - 1] + 2 * dp[num - 2])
return dp[-1] % 10007
def main():
print(two_n_tiling(int(sys.stdin.readline())))
if __name__ == '__main__':
main()✍️풀이과정
다이나믹 프로그래밍(DP) 풀이 방법론
핵심: 큰 문제를 작은 문제로 나누는 것
- 문제를 DP로 풀 수 있는 지 판단 : 중복이 되는 부분이 있는가
- 상태 정의 : 작은 수로 직접 해보면서 나열해본다
- 점화식 세우기
여기서는 가장 마지막에 놓은 타일에 따라 경우의 수를 나누어 생각해야한다.
- 마지막에 놓은 타일이 1×2(세로로 긴) 타일인 경우
이 타일로 2×1 공간을 채웁니다. 그러면 남는 부분은 2×(n-1) 크기가 됩니다. 따라서 이 경우의 수는 “2×(n-1)을 채우는 방법의 수”인 dp[n-1]과 동일합니다.2.마지막에 놓은 타일이 2×1(가로로 긴) 두 개를 위아래로 놓은 경우
가로 타일 두 개로 2×2 공간을 채웁니다(각각 2×1 크기). 남는 부분은 2×(n-2) 크기가 됩니다. 이 경우는 “2×(n-2)을 채우는 방법의 수”인 dp[n-2]에 해당합니다.
- 마지막에 놓은 타일이 2×2(정사각형)인 경우
이 타일 한 장으로 2×2 공간을 채웁니다. 남는 부분은 2×(n-2) 크기가 됩니다. 이 경우의 수 역시 “2×(n-2)을 채우는 방법의 수”인 dp[n-2]에 해당합니다.
결과적으로, 위 2)와 3)이 둘 다 2×(n-2)을 채우는 경우의 수를 사용하지만, 타일 형태가 다르므로 dp[n-2]를 두 번 더하면 됨.
dp[n] = dp[n-1] + 2 * dp[n-2]
- 초기값 설정 : 점화식에 필요한 초기값을 설정한다.
이런 식으로 설정하면 된다.
근데 코드가 틀렸다고 나오길래 다시 살펴보니 10007로 나누는 것을 까먹은 것이었다.
앞으로는 문제를 읽고 코드 위에 주석을 다는 습관을 길러야겠다.
🧠 코드 리뷰
- 공간 최적화 : dp 리스트를 사용하지 않고 두 개의 변수만 사용하여 계산할 수 있습니다.
🛠️AI 개선 코드
import sys
def two_n_tiling_optimized(number):
if number == 1:
return 1
elif number == 2:
return 3
prev2 = 1 # dp[1]
prev1 = 3 # dp[2]
for _ in range(3, number + 1):
current = (prev1 + 2 * prev2) % 10007
prev2, prev1 = prev1, current
return prev1
def main():
try:
n = int(sys.stdin.readline())
if n <= 0:
print(0)
else:
print(two_n_tiling_optimized(n))
except:
print(0)
if __name__ == '__main__':
main()
💻결과
🖱️참고 링크
우물 안에서 무언가 만드는 사람