해당 게시글에서는 [백준] 11726 2xn 타일링 문제를 해설하고 Python을 이용하여 풀고자 한다.
🤔 접근법
문제 풀이 방식을 빠르게 알고싶다면 💡문제 풀이 부분 부터 봐주세요 :)
11726번 문제는 DP(다이나믹 프로그래밍)에 대한 문제로 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법하는 방식의 알고리즘이다.
현재 바킹독의 알고리즘 문제집을 참고하여 알고리즘 별로 문제를 풀고있기 때문에 이 문제가 DP 문제라는 것을 알고 있었다. 하지만 해당 문제를 처음 접했을 때는 DP 문제라는 게 도저히 와닿지 않았다.
결과적으로 혼자 풀긴 했지만 만약 DP 문제인 것을 몰랐더라면? 나는 못 풀었을 것이라고 생각한다.
DP 문제의 경우 제시한 상황에 대한 규칙, 즉 점화식만 알면 어렵지 않기 때문에 직접 손으로 그려가며 규칙을 찾으려고 했다.
N번째 직사각형의 경우에 N-1번째, N-2번째, N-3번째, … 등과 어떤 규칙이 있는지 찾아보려고 했지만 도저히 찾을 수 없었다.
이러한 고민을 계속 하다가 든 생각이 '왜 굳이 기하적으로 생각하고 있지? 직사각형의 가로의 길이를 1과 2의 조합으로 나누면 되지 않나?'었다.
💡 문제 풀이
즉, 2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수는 직사각형의 가로를 1과 2의 조합으로 나누는 경우와 동일하다!
이때 1(2x1 타일)과 2(1x2 타일)로 나누는 것은 2x1타일이 들어갈 자리와 1x2 타일이 들어갈 자리를 분배하는 것을 의미한다.
예를 들어 n이 3이라고 하면, 3을 1과 2의 조합으로 다음과 같이 나눌 수 있다.
- 1+1+1
- 2+1
- 1+2
1의 위치에는 2x1의 타일을, 2의 위치에는 1x2의 타일을 넣으면 되는 것이다.
사실 1, 2, 3 더하기 문제와 접근 방식이 동일한 문제였다. 해당 문제를 풀었다면 유사한 방식으로 접근하면 된다.
그렇다면 이제 점화식을 어떻게 작성할 것인가? 정답을 알기 전에 다음 이미지를 통해 직접 규칙을 찾기를 바란다.
위 이미지를 통해 규칙을 찾기 어렵다면 아래 이미지도 참고하자!
부연 설명을 하자면, 앞서 2xn 직사각형을 타일링 하기 위해선 n을 1과 2의 조합으로 나눠야 된다고 했고, 그럼 모든 경우에 대해 숫자의 끝은 1 아니면 2일 것이다.
- 끝이 1인 경우는 앞에 있는 숫자의 합이 n-1인 경우, 즉 앞부분은 2x(n-1) 타일링이 됐음을 의미
- 끝이 2인 경우는 앞에 있는 숫자의 합이 n-2인 경우, 즉 앞부분은 2x(n-2) 타일링이 됐음을 의미
2xn 타일링은 끝이 1인 경우와 끝이 2인 경우의 합인, 2x(n-1) 타일링 + 2x(n-2) 타일링인 것이다.
이를 코드로 나타내면 다음과 같다.
1
dp[i] = dp[i-1] + dp[i-2]
📂 코드
위 문제 풀이 방식을 통해 해당 문제를 풀어낸 필자의 코드는 다음과 같다.
1
2
3
4
5
N = int(input())
dp = [0, 1, 2]
for i in range(3, N+1):
dp.append(dp[i-1]+dp[i-2])
print(dp[N]%10007)