득이공간
[백준 C++] 11726 2xn 타일링 - 다이나믹프로그래밍 본문
#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;
DP[2] = 2;
for (int i = 3; i <= N; ++i)
{
DP[i] = DP[i - 1] + DP[i - 2] % 10007;
}
cout << DP[N] % 10007;
}
DP 문제입니다.
타일의 윗줄만 보았을 때 1칸 또는 2칸의 덧셈을 나열하는 경우의 수를 구하도록 점화식을 세웠습니다.
문제의 예시 그림에 경우는 1 + 1 + 2 + 1라고 볼 수 있습니다.
그리고 테이블에 값을 저장할 때도 mod를 해주어야 해당 값이 자료형의 크기를 넘어가지 않습니다.
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 C++] 13305 주유소 - 그리디 (0) | 2024.02.05 |
---|---|
[백준 C++] 1541 잃어버린 괄호 - 그리디 (1) | 2024.02.05 |
[백준 C++] 9095 1, 2, 3 더하기 - 다이나믹프로그래밍 (0) | 2024.02.04 |
[백준 C++] 1003 피보나치 함수 - 다이나믹프로그래밍 (0) | 2024.02.04 |
[백준 C++] 11659 구간 합 구하기 4 - 자료구조 (0) | 2024.02.03 |