[알고리즘][DP, 수학] 2839번 설탕 배달 | baekjoon 문제 풀이

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

2839번: 설탕 배달

 

 

 

풀이

 

경우를 생각하여 계산해주었다.

만약 N이 5로 나누어 떨어지는 게 아니라면

계속 3으로 빼주고

5로 나누어 떨어지는 순간이 올 때 호다닥 5로 빼준다.

 

근데 DP로도 풀어볼 수 있을 것 같은데, DP 식 짜는 게 아직 익숙하지 않고 넘 어렵다... 그래서 DP로 짜는 방법은 블로그를 참고하여 풀었다.

 

<수학을 이용한 코드>

#include <iostream>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	int N, count = 0; cin >> N;

	bool isSuccessful = true;

	while (isSuccessful & (N != 0)) {
		if (N % 5 == 0) { // 5로 나누어 떨어지면 빼기 진행
			N -= 5;
			count++;
		}
		else { // 아니면 3으로 뺄 수 밖에 없음
			if (N >= 3) { 
				N -= 3;
				count++;
			}
			else isSuccessful = false;
		}
	}

	if (isSuccessful) cout << count;
	else cout << -1;
}

 

 

<DP를 이용한 코드>

#include <iostream>
using namespace std;

int dp[5001]; // global 변수라서 0으로 초기화 되어있음

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int n;
	cin >> n;
	
	dp[3] = dp[5] = 1; // 3kg짜리와 5kg짜리를 만드는 최소 봉지수는 1

	for (int i = 6; i <= n; i++) { // 5 다음인 6부터 순회
		if (dp[i - 3]) // 만약 i-3이 1 이상일 경우
			dp[i] = dp[i - 3] + 1;

		if (dp[i - 5]) // 만약 i-5가 1 이상일 경우
			// dp가 i-3을 통해 계산이 되었을 경우, i-5와도 비교하고 최소값 사용
			// 아닐 경우 i-5를 통해 업데이트
			dp[i] = (dp[i] ? min(dp[i], dp[i - 5] + 1) : dp[i - 5] + 1);
	}
	cout << (dp[n] == 0 ? -1 : dp[n]) << '\n';
	return 0;
}

 

 

이해가 되긴 했음...

 

근데 스스로 DP 코드 짜는 게 왤케 익숙하지 않을까!!!!!!!!!!!!!!!

 

=> 더 많이 풀어보는 게 답이다 채숭아 정신 차려랏~~~~