백준 15989번 1, 2, 3 더하기 4 C++ 다이나믹 프로그래밍, DP

리뷰

 

입력되는 숫자의 범위가 10000이므로 10000까지의 값을 미리 구해놓은 뒤 O(1)의 속도로 쿼리를 처리하는 문제

https://www.acmicpc.net/problem/15989

 

문제 풀이

1. 정수형 배열 dp를 10001 크기로 설정한 후, dp[1], dp[2], dp[3]은 1로 초기화를 해준다.
2. n이 10인 경우까지 손코딩을 해보면 쉽게 점화식을 도출할 수 있다.
3. 점화식 : dp[i] = dp[i - 3] + i / 2 + 1
4. t값을 입력 받고 t번에 입력되는 테스트케이스를 dp의 인덱스로 출력해 주면 된다.

 

참고 사항

n = 1 ~ 10까지의 케이스

1

1 1
2

1 1 1
2 1
3

1 1 1 1
2 1 1
2 2
3 1

1 1 1 1 1
2 1 1 1
2 2 1
3 1 1
3 2

1 1 1 1 1 1
2 1 1 1 1
2 2 1 1
2 2 2
3 1 1 1
3 2 1
3 3

1 1 1 1 1 1 1
2 1 1 1 1 1
2 2 1 1 1
2 2 2 1
3 1 1 1 1
3 2 1 1
3 2 2
3 3 1

1 1 1 1 1 1 1 1
2 1 1 1 1 1 1
2 2 1 1 1 1
2 2 2 1 1
2 2 2 2
3 1 1 1 1 1
3 2 1 1 1
3 2 2 1
3 3 1 1
3 3 2

1 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1
2 2 1 1 1 1 1
2 2 2 1 1 1
2 2 2 2 1
3 1 1 1 1 1 1
3 2 1 1 1 1
3 2 2 1 1
3 2 2 2
3 3 1 1 1
3 3 2 1
3 3 3

1 1 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1
2 2 1 1 1 1 1 1
2 2 2 1 1 1 1
2 2 2 2 1 1
2 2 2 2 2
3 1 1 1 1 1 1 1
3 2 1 1 1 1 1
3 2 2 1 1 1
3 2 2 2 1
3 3 1 1 1 1
3 3 2 1 1
3 3 2 2
3 3 3 1

 

 

정답 코드

#include<iostream>

using namespace std;

int dp[10001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 1; i < 4; i++) dp[i] = i;
	for (int i = 4; i < 10001; i++) dp[i] = dp[i - 3] + i / 2 + 1;

	int t; cin >> t;
	while (t--) {
		int a; cin >> a;
		cout << dp[a] << "\n";
	}
}