2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×17 직사각형을 채운 한 가지 예이다.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다.
각 테스트 케이스는 한 줄로 이루어져 있으며, 정수 n이 주어진다.
출력
입력으로 주어지는 각각의 n마다, 2×n 직사각형을 채우는 방법의 수를 출력한다. (0 ≤ n ≤ 250)
반응형
풀이
"""백준에서 정답으로 인정하는 코드"""
import sys
input = sys.stdin.readline
DP = [0 for _ in range(251)]
DP[0] = 1
DP[1] = 1
for i in range(2,251):
DP[i] = DP[i-1] + 2*DP[i-2]
while (True):
try:
n = int(input().rstrip())
print(DP[n])
except:
break
728x90
문제를 보자마자 생각나는 DP풀이법이다.
노트에 하나하나 그려서 세어본건 안 비밀
숫자에서 규칙을 찾아 DP풀이법으로 문제를 해결했다.
DP는 수학에서 점화식 풀이를 알고리즘 문제 풀이에 적용한 것이라고 생각하면 편하다.
이 문제에서 어렵게 느껴질 수 있는 부분이 2가지가 있다.
첫 번째로는 DP풀이를 생각해내는 것이다.
알고리즘 문제를 좀 풀어봤다 하는 사람들이라면 문제를 보자마자 DP가 생각나는 문제이다.
그에 반해 DP문제를 처음 접한 사람이라면 감도 안 잡힐 수 있다고 생각한다.
많이 풀어보는 방법밖에 없는 것 같다.
두 번째로는 대부분의 백준 문제와 다르게 입력값의 제한이 없다는 것이다.
대부분 백준 문제들은 N과 같은 반복실행 횟수를 입력값으로 제공한다.
다만, 해당 문제에서는 반복실행 횟수가 정해져 있지 않고 while과 try except 구문으로 입력값이 없을 때를 구분하여 프로그램을 종료하여야 한다.
이 문제에는 그보다 더 큰 문제가 있다.
2*n 범위에서 n이 0일 때 답이 무엇이라고 생각하는가?
타일이 들어갈 공간이 존재하지 않으므로 0이 맞는 풀이라고 생각한다.
필자도 그렇게 생각하고 다음과 같은 코드를 제출했다.
"""내가 생각하는 옳은 풀이 (백준에서 통과 안 됨)"""
import sys
input = sys.stdin.readline
DP = [0 for _ in range(251)]
DP[0] = 1
DP[1] = 1
for i in range(2,251):
DP[i] = DP[i-1] + 2*DP[i-2]
while (True):
try:
n = int(input().rstrip())
if n == 0:
print(0)
else:
print(DP[n])
except:
break
