728x90
문제
https://www.acmicpc.net/problem/11726
문제이해
- 첫째 줄에 n을 입력합니다.
- 정답이 되는 방법의 수를 10007로 나눈 나머지를 출력합니다.
이 문제는 다이나믹 프로그래밍을 사용해야합니다. 방법의 수를 찾기 위해서는 우선 점화식부터 찾아야합니다.
이를 배열로써 설명해보겠습니다. dp[i]는 2xi 크기의 직사각형을 채우는 방법의 수를 의미합니다.
dp[1]은 1, dp[2]는 2, dp[3]은 3이라고 할 수 있습니다.
그렇다면 dp[4]의 값은 얼마일까요 dp[2]의 상태에서 가로블럭 2개짜리를 오른쪽에 놓으면 dp[4]가 될 수 있습니다. dp[3]의 상태에서 세로블럭 1개짜리를 오른쪽에 놓으면 dp[4]가 될 수 있습니다. 따라서 dp[4]는 dp[3]의 값과 dp[2]의 값을 더하면 나옵니다.
이를 통해 점화식이 dp[i+2] = dp[i+1] + dp[i]라는 것을 확인했습니다. 2xn 크기의 직사각형을 채우는 방법의 수를 알기 위해서는 dp[n]의 값을 확인하기만 하면 됩니다.
이 문제에서는 dp[n]의 값을 10007로 나누어서 출력해야 합니다. 점화식을 통해 저장될 dp[n]의 값들을 10007로 나눈 나머지로 저장하기만 해도 모든 값들이 dp[n]을 10007로 나눈 나머지로 저장되게 될겁니다.
다음은 위의 내용을 토대로 만든 코드입니다.
문제풀이
#include <iostream>
#include <vector>
using namespace std;
vector<long long> dp(1001);
void method() {
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
for (int i{ 4 }; i < dp.size(); i++) {
dp[i] = dp[i - 1] + 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];
}
문제후기
점화식을 찾는건 쉬웠으나 10007로 나눈다는 것에서 헷갈렸던 문제였습니다.
728x90
'Coding' 카테고리의 다른 글
[C++]백준 1463번: 1로 만들기 (0) | 2023.08.02 |
---|---|
[C++]백준 11727번: 2xn 타일링 2 (0) | 2023.08.02 |
[C++]백준 11286번: 절댓값 힙 (0) | 2023.08.01 |
[C++]백준 1422번: 숫자의 신 (0) | 2023.07.27 |
[C++]백준 17070번: 파이프 옮기기 1 (0) | 2023.07.25 |