득이공간
[백준 C++] 11727 2×n 타일링 2 - 다이나믹프로그래밍 본문
#include <iostream>
using namespace std;
int DP[1001];
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int N;
cin >> N;
DP[1] = 1;
for (int i = 2; i <= N; ++i)
{
if ((i - 1) % 2 == 1)
{
DP[i] = DP[i - 1] * 2 + 1;
}
else
{
DP[i] = DP[i - 1] * 2 - 1;
}
DP[i] %= 10007;
}
cout << DP[N];
}
점화식을 도출해서 푸는 다이나믹 프로그래밍 유형의 문제입니다.
n이 1~6일 때의 각 경우의 수 1, 3, 5, 11, 21, 43 에 따라 일반화 된 점화식은 다음과 같습니다.
DP[i] = DP[i -1] * 2 + 1 (i-1이 홀수 일때)
DP[i] = DP[i -1] * 2 - 1 (i-1이 짝수 일때)
다른 분들의 풀이를 보니 다음과 같은 점화식을 사용해서 푸는 방법도 존재했습니다.
DP[i] = DP[i - 1] + DP[i -2] * 2
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 C++] 11279 최대 힙 - 우선순위큐 (0) | 2024.02.15 |
---|---|
[백준 C++] 17626 Four Squares - 다이나믹프로그래밍 (0) | 2024.02.15 |
[백준 C++] 9461 파도반 수열 - 다이나믹프로그래밍 (0) | 2024.02.15 |
[백준 C++] 9375 패션왕 신해빈 - 조합론 (0) | 2024.02.15 |
[백준 C++] 2579 계단 오르기 - 다이나믹프로그래밍 (0) | 2024.02.15 |