[알고리즘/DP] 백준 BOJ 11726 2xn 타일링

BOJ 11726 2xn 타일링

 

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1

2

예제 출력 1

2

예제 입력 2

9

예제 출력 2

55

 

 

---

💡나의 문제 풀이

문제 해결 아이디어

• 세로를 기준으로 다음과 같이 나타낼 수 있다.
  • n=1 [1,2] 1개→ 1
  • n=2 [2,2] 2개→ 11 (가로1 2개) / 2 (가로 2 2개)
  • n=3 [3,2] 3개 → 111 (가로1 3개) / 1 2 (가로1 1개, 가로2 2개) , 21 (가로2 2개, 가로1 1개)
  • n=4 [4,2] 5개 → 1111 (3) / 121, 211 (3) / 112, 22(2)
  • n=5 [5,2] → 11111 (4) / 1211, 2111 (4) / 1121, 221 (4) / 1112 (3) / 122, 212 (3)
  • n=6 [6,2] → 11111 (5) / 11211, 12112, 21112 (5) / 11121 (5) / 11121 (5) / 1221, 2121 (5) / 11112(4) / 11212(5) , 12112(5) ….
• 위와 같이 n=1일때 1개, n=2일때 2개이며, n=3에서부터 앞의 두 단계에서 만들어진 도형에 각각 한 개 [1,2] 씩 덧붙인 것과 같기 때문에 dp[i]의 값은 이전 2개 값의 합(dp[i-1]+dp[i-2])과 같다.

 

---

작성 코드

• 런타임 에러 발생

n = int(input())
dp = [0]*(n+1)

dp[1] = 1
dp[2] = 2
for i in range(3, n+1):
  dp[i] = dp[i-1] + dp[i-2]

print(dp[n]%10007)

• 런타임 에러 발생하여 다음과 같이 코드를 약간 수정했더니 해결 완료!

n = int(input())
dp =[1,2]
for i in range(2, n+1):
  dp.append(dp[i-1] + dp[i-2])

print(dp[n-1]%10007)

 

---

답안 코드

• 작성 코드와 동일

s = [0, 1, 2]
for i in range(3, 1001):
  s.append(s[i - 2] + s[i - 1])
n = int(input())
print(s[n] % 10007)

 

리뷰 및 점검

• 이전에 풀었던 [9095 1,2,3 더하기] 문제와 도형 문제라는 점을 제외하고는 아이디어가 거의 유사하여, 문제 이해 후에는 금방 규칙을 이해했고 문제 해결 아이디어를 따낼 수 있었다.
• 이제 DP문제를 어떠한 방식으로 접근해야 하는지 약간 감을 잡은 것 같기도 하다. 재밌어 지고 있다! 🙂