문제 설명
2*N 타일 채우기 문제는 주어진 2xN 크기의 공간을 1×2 크기의 타일로 채우는 방법의 수를 구하는 문제입니다.
타일은 가로로 또는 세로로 배치할 수 있으며, 전체 2xN 공간을 완전히 채워야 합니다.
이 문제의 핵심은 조합의 수를 계산하는 것이며, 동적 프로그래밍(Dynamic Programming) 기법을 통해 해결할 수 있습니다.
입력 형식
정수 N이 주어집니다. (1 ≤ N ≤ 30)
출력 형식
2xN 공간을 채우는 방법의 수를 정수로 출력합니다.
문제 풀이 과정
2*N 타일 채우기 문제를 해결하기 위해서, 우리는 몇 가지 예제를 통해 문제의 패턴을 찾아야 합니다.
먼저 N이 1일 때와 N이 2일 때의 경우를 생각해봅시다.
예제
- N = 1:
- 1가지 방법: 세로로 1개 타일 배치
- N = 2:
- 2가지 방법: 가로로 2개 타일을 배치하거나, 세로로 1개 타일 2개 배치
여기서 우리는 다음과 같은 패턴을 발견할 수 있습니다.
N이 커짐에 따라 각 경우를 다음과 같이 나누어 볼 수 있습니다.
– N번째 칸에 타일을 가로로 넣으면, 이전 N-1개의 칸이 남습니다.
– N번째 칸에 타일을 세로로 넣으면, 이전 N-2개의 칸이 남습니다.
따라서, 점화식은 다음과 같이 표현할 수 있습니다:
dp[n] = dp[n-1] + dp[n-2]
이 점화식을 설정했을 때, 초기값을 설정해야 합니다.
dp[1] = 1 (1×2 타일로 세로 배치), dp[2] = 2 (가로 2개 또는 세로 1개 + 세로 1개) 입니다.
이제 이 점화식을 바탕으로 N을 입력받아 방법의 수를 계산하는 C++ 프로그램을 작성해 보겠습니다.
C++ 코드 구현
#include
using namespace std;
int main() {
int N;
cin >> N;
int dp[31] = {0};
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= N; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
cout << dp[N] << endl;
return 0;
}
위 코드는 입력받은 N에 대해 dp 배열을 생성하고, 동적 프로그래밍 기법을 사용하여 각 경우의 수를 계산합니다.
마지막에 dp[N]을 출력하여 2xN 타일 채우기 방법의 수를 구합니다.
시간 복잡도
이 알고리즘의 시간 복잡도는 O(N)입니다.
이는 for 루프를 N번 반복하기 때문입니다.
공간 복잡도 또한 O(N)으로 dp 배열을 사용하기 때문입니다.
결론
2*N 타일 채우기 문제는 동적 프로그래밍의 전형적인 예입니다.
문제를 작게 나누어 재귀적으로 해결하는 점화식을 만들고, 이를 통해 문제를 해결하는 것이 핵심입니다.
코딩 테스트에서도 자주 출제되는 문제이니만큼, 이해하고 반복 연습하여 익혀두는 것이 중요합니다.