Dynamic Programming

큰 문제를 작은 문제부터 해결하여 계산하기(분할 정복 기법) : 1차원 배열

1. 5원을 먼저 개수를 정하고, 남은 금액에 대해서 3원의 개수를 정하기 -> X

• 예외가 발생

큰 문제를 작은 문제부터 해결하여 계산하기(분할 정복 기법) : 1차원 배열(설탕배달)

• 배열의 크기 : 19
• 배열의 이름 : dp
• N : 18
• 구하고자 하는 것 : f18 = dp[18]
  

ex6) dp[6]

• dp[6-5] = dp[1] = X
• dp[6-3] = dp[3] = 1
• dp[6] = min(dp[1]+1, dp[3]+1) = dp[3]+1 = 1+1 = 2
• dp[6] = 2

ex7) dp[7]

• dp[7-5] = dp[2] = X
• dp[7-3] = dp[4] = X
• dp[7] = X

Dynamic Programming 푸는 방법

1. trivial case 찾아내기 (쉽게 알 수 있는 것들 일단 찾기)
2. non-trivial case 찾아내기 (점화식 필요)

코드 v1

#include <iostream>
#include <algorithm>
using namespace std;

#define X -1

int dp[5010] = { 0, X, X, 1, X, 1 };
int N;

int main() {
	scanf("%d", &N);
	for (int i = 6; i <= N; i++) {
		if (dp[i - 3] == X && dp[i - 5] == X) {
			dp[i] = X;
			continue;
		}
		if (dp[i - 3] == X || dp[i - 5] == X) {
			dp[i] = max(dp[i - 3] + 1, dp[i - 5] + 1);
			continue;
		}
		dp[i] = min(dp[i - 3] + 1, dp[i - 5] + 1);
	}
	printf("%d", dp[N]);
}

코드 v2

#include <iostream>
#include <algorithm>
using namespace std;

#define X 5000

int dp[5010] = { 0, X, X, 1, X, 1 };
int N;

int main() {
	scanf("%d", &N);
	for (int i = 6; i <= N; i++)
		dp[i] = min(dp[i - 3] + 1, dp[i - 5] + 1);

	if (dp[N] >= X) {
		printf("-1");
		return 0;
	}

	printf("%d", dp[N]);
}

조건문 이해

if (dp[N] >= X) {
    printf("-1");
    return 0;
}

• X는 5000으로 정의되어 있습니다. 이는 임의로 큰 값으로 설정된 것입니다.
• dp 배열의 초기화 값으로 사용되며, 특정 정수를 3과 5로 나눌 수 없는 경우에 해당하는 값을 나타냅니다.
• dp[N] >= X 조건은 dp[N]이 초기화 값인 5000 이상인 경우, 즉, 입력된 N을 3과 5의 조합으로 나눌 수 없음을 의미합니다

따라서, 이 조건이 참이라면:

• printf("-1");로 -1을 출력합니다. 이는 문제의 조건에서 N을 3과 5로 나눌 수 없음을 나타냅니다.
• return 0;으로 프로그램을 종료합니다.
• 만약 dp[N]이 5000 미만이라면, 이는 N을 3과 5의 조합으로 나눌 수 있음을 의미하며, 그 경우 dp[N] 값을 출력합니다.

-> 이 조건문은 N을 3과 5로 나눌 수 없는 경우를 처리하는 부분입니다. 초기화 값 X (5000)를 사용하여 특정 값을 3과 5로 나눌 수 없는 경우를 나타내며, dp[N]이 이 값 이상이라면 -1을 출력하고 프로그램을 종료합니다. 그렇지 않다면 dp[N] 값을 출력하여 최소 횟수를 나타냅니다.

-> 위의 for문에서 `dp[i] = min(dp[i - 3] + 1, dp[i - 5] + 1);` 이 코드를 돌려서 dp[i-3]+1도, dp[i-5]+1 모두 X라면 dp[i] = X 이므로 이거를 다 모아서 나중에 if문으로 처리하는 것이다!!!