문제
https://www.acmicpc.net/problem/11727
문제이해
- 째 줄에 n을 입력합니다.
- 2xn 크기의 직사각형을 채우는 방법을 10007로 나눈 값을 출력합니다.
이 문제는 다이나믹 프로그래밍을 사용하는 문제입니다. 사용할 수 있는 블록은 2x1로 된 가로블록, 1x2로 된 세로 블록, 2x2로 된 정사각형 블록으로 총 3개가 있습니다.
점화식을 찾기 위해 우선 배열을 통해 설명해 보겠습니다. 2xi 크기의 직사각형을 채우는 방법을 의미합니다.
dp [1]은 세로블록 한 개의 경우밖에 없으므로 1입니다.
dp [2]는 세로블록 두개 또는 가로블럭 두개 또는 정사각형 블럭 한 개의 경우가 있으므로 3입니다.
dp [3]은 확인해 보면 5입니다.
dp [2]를 통해 dp [4]를 만드는 방법은 오른쪽에 가로블록 두개를 놓거나 세로블럭 두 개를 놓거나 정사각형 블럭 한 개를 놓는 방법이 있습니다.
dp [3]을 통해 dp [4]를 만드는 방법은 오른쪽에 세로블록 한 개를 놓는 방법이 있습니다. 다만 dp [3]의 오른쪽에 세로블록 한 개를 놓는 방법은 dp [2]를 통해 dp [4]를 만드는 방법 중 한 개와 겹치기 때문에 dp [2]에서 dp [4]를 만드는 방법을 총 두 개뿐인 것으로 해야 합니다.
이를 통해 얻을 수 있는 점화식은
dp [i + 2] = dp[i + 1] + dp [i] + dp [i]이고 이는 dp [i + 2] = dp[i + 1] + 2 * dp [i]라고 할 수 있습니다.
아래의 코드는 해당 점화식을 통해 dp [i]의 값을 알아내 출력하는 정답 코드입니다.
문제풀이
#include <iostream>
#include <vector>
using namespace std;
vector<long long> dp(1001);
void method() {
dp[1] = 1;
dp[2] = 3;
for (int i{ 3 }; i < dp.size(); i++) {
dp[i] = dp[i - 1] + 2 * dp[i - 2];
dp[i] %= 10007;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
method();
int N;
cin >> N;
cout << dp[N];
}
문제후기
점화식이 찾기 쉬워 어렵지 않은 문제였습니다.
'Coding' 카테고리의 다른 글
[C++]백준 5014번: 스타트링크 (0) | 2023.08.03 |
---|---|
[C++]백준 1463번: 1로 만들기 (0) | 2023.08.02 |
[C++]백준 11726번: 2xn 타일링 (0) | 2023.08.01 |
[C++]백준 11286번: 절댓값 힙 (0) | 2023.08.01 |
[C++]백준 1422번: 숫자의 신 (0) | 2023.07.27 |