백준 11726번
오늘 풀어본 문제는 백준의 11726번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
$2\times n$ 크기의 직사각형을 $1\times 2$, $2\times 1$ 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 $2\times 5$ 크기의 직사각형을 채운 한 가지 방법의 예이다.
입력
첫째 줄에 $n$이 주어진다. $(1 \leq n \leq 1,000)$
출력
첫째 줄에 $2\times n$ 크기의 직사각형을 채우는 방법의 수를 $10,007$로 나눈 나머지를 출력한다.
풀이과정
첫 번째 시도
문제를 읽자마자 DP를 이용해야 하는 문제라는 것 정도는 눈치챌 수 있었다. 그 다음은 어떻게 관계가 구성되느냐였는데, 블럭들을 잘 보니 가운데 가로선을 기준으로 위 아래가 대칭이라는 것을 확인할 수 있었다. 대칭이 아니도록 가로로 누운 블럭을 놓아보려고 했지만, 불가능했다.
그래서 문제를 좀 더 단순화하여 $1 \times n$ 만큼 칸이 있다고 생각하고, 한 칸만 채우거나 두 칸을 채우는 방식으로 모든 칸을 채우는 문제로 생각하여 풀이를 진행해보았다.
$k$ 번째 칸 까지 채우는 방법의 수는, $k-1$ 번째 칸 까지 채운 후 한 칸 짜리 블럭을 놓는 방식의 수와, $k-2$ 번째 칸 까지 채운 후 두 칸 짜리 블럭을 놓는 방식의 수를 합하면 된다는 것을 알 수 있었고, 이를 이용하여 코드를 작성하였다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> graph(100001);
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
int dp[1001] = { 0, };
dp[0] = dp[1] = 1;
cin >> n;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
cout << dp[n];
return 0;
}
실행 결과 바로 틀렸습니다가 나왔다…
두 번째 시도
문제 조건을 다시 읽어본 결과 방법의 수를 $10,007$ 로 나누어야 한다는 조건이 적혀있었다. 문제를 대충 읽어버린 것이다. 이 조건이 기존의 코드에서 수정하기 어려운 것이 아니라서 천만다행이었다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
int dp[1001] = { 0, };
dp[0] = dp[1] = 1;
cin >> n;
for (int i = 2; i <= n; i++) {
dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
}
cout << dp[n];
return 0;
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
오늘은 왜 갑자기 CLASS 4가 아니라 CLASS 3 문제를 가져왔냐고 의문을 품을 수 있다. 그건 오늘 내가 풀어 보려고 했던 문제가 제대로 해결되지 않아 시간을 너무 허비했기 때문이다. 그래서 글도 못 쓰는 사태가 벌어질까 해서 CLASS 3의 문제를 하나 잡아다가 푼 것이다.
그렇다고는 해도, 이 문제에서 배울 점이 없었던 것은 아니다. 앞에 풀이에서도 이야기 했지만, 문제 조건을 똑바로 읽지 않아서 어이없는 실수가 벌어졌다. 급하고 귀찮더라도 문제 조건은 꼼꼼히 읽는 습관을 들여야겠다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/11726