https://www.acmicpc.net/problem/11726
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
#전체 코드
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
string A, B;
cin >> A >> B;
int ans = 0;
int B_index = B.length() - 1;
for (int i = A.length()-1; i >= 0; i--) {
if (A[i] == B[B_index]) {
B_index --;
}
else ans++;
}
sort(A.begin(), A.end());
sort(B.begin(), B.end());
if (A == B) cout << ans;
else cout << -1;
return 0;
}
문제 해설
문제는 2×n 크기의 직사각형을 1×2 또는 2×1 크기의 타일로 채울 수 있는 방법의 수를 찾는 것입니다. 그러나 찾은 수가 매우 클 수 있으므로, 10,007로 나눈 나머지를 출력해야 합니다.
코드 설명
이 문제를 해결하기 위해 동적 프로그래밍(DP)이라는 방법을 사용하고 있습니다. 아래에서 코드의 각 부분에 대해 설명하겠습니다:
cpp
Copy code
int n; cin >> n;
int tile[1001] = { 0 };
위에서는 n을 입력 받고, 최대 크기가 1001인 배열을 초기화하고 있습니다. 배열 tile은 각 인덱스에서 가능한 타일링 방법의 수를 저장할 것입니다.
cpp
Copy code
tile[0] = 1;
tile[1] = 1;
tile[2] = 2;
2×0, 2×1, 2×2 크기의 직사각형을 타일로 채우는 방법의 수는 각각 1, 1, 2가 됩니다. 이는 초기 조건으로 설정됩니다.
cpp
Copy code
for (int i = 3; i <= n; i++) {
tile[i] = (tile[i - 1] + tile[i - 2])%10007;
}
이 반복문은 DP 접근법의 핵심 부분입니다. 각 i에 대해 (i-1)과 (i-2)에서 가능한 타일링 방법의 수의 합을 구하며, 이를 10,007로 나눈 나머지를 저장합니다. 이는 2×i 크기의 직사각형을 채우는 마지막 부분이 2×1 또는 1×2 타일로 채워지는 두 가지 경우를 고려한 것입니다.
cpp
Copy code
cout << tile[n];
마지막으로, 2×n 크기의 직사각형을 채울 수 있는 방법의 수를 출력합니다. 이 값은 위의 반복문에서 tile[n]에 저장되어 있습니다.
결론
이 코드는 동적 프로그래밍을 사용하여 문제를 효율적으로 해결합니다. 단계별로 이전 결과를 이용해 현재 문제를 해결함으로써, 최종적으로 원하는 크기의 직사각형에 대한 해결책을 찾을 수 있습니다.
'[백준] > C++' 카테고리의 다른 글
| 백준 1068번 트리 [C++] (0) | 2023.09.18 |
|---|---|
| 백준 1149번 RGB거리 [C++] (0) | 2023.09.17 |
| 백준 13019번 A를 B로 [C++] (0) | 2023.09.17 |
| 백준 7576번 토마토 [C++] (0) | 2023.09.14 |
| 백준 7562번 나이트의 이동 [C++] (0) | 2023.09.14 |
