[백준 BOJ] 2839번 설탕 배달 (C++/cpp)

문제 설명

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

2839번: 설탕 배달

 

 

접근 방법 - 그리디 알고리즘을 이용한 연산 문제

백준의 2839번 문제는 그리디 알고리즘을 응용하여 해결해야 하는 문제이다.

해당 문제는, 주어진 설탕을 3kg, 5kg 봉지로 묶을 때 필요한 봉지의 최소 개수를 출력해야 하는 문제이다.

여기서 그리디 알고리즘이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하는 알고리즘"이다.

이 알고리즘과 관련하여 이전에 풀었던 문제에 대한 설명을 작성한 것이 있으니, 아래의 링크도 함께 참고하면 좋을 것이다.

https://smary-it.tistory.com/203

[백준 BOJ] 11047번 동전 0 (C++/cpp)

사실 필자는 아직 그리디 알고리즘이 익숙하지 않아서 설명이 많이 미숙할 수도 있다. (크흠)

하지만 이 알고리즘이 어색하거나 해당 문제를 푸는 데에 어려움을 겪고 있다면, 아래의 설명과 코드가 도움이 될 것이다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 설탕의 무게(n)를 입력받는다.

 

2) 설탕을 포장하는 데에 사용할 봉지의 최소 개수를 저장할 변수 cnt를 0으로 초기화하여 선언한다.

 

3) n이 3 이상의 값을 가지고 있다면 해당 반복문을 수행하여 아래의 연산을 취한다.

(다만, 입력값에서부터 3 아래의 값을 가지고 있다면 애진작에 이 반복문을 수행하지 않도록 한다.)

- 만일 현재 n 값이 5로 나누어 떨어진다면, 이는 5kg 봉지로만 현재 설탕을 포장할 수 있는 상태임을 뜻한다.

따라서 이 경우에는, cnt에 현재 n값을 5로 나눈 몫을 더한다. 그리고 n 값을 0으로 한 뒤에 해당 반복문을 탈출한다.

- 현재 n 값이 5로 나누어 떨어지지 않는다면, 이는 3kg 봉지를 하나 이상은 사용해야 하는 상태임을 뜻한다.

따라서 이 경우엔, n 값에서 3을 뺀 뒤 cnt에 1을 더하고 해당 반복문의 처음으로 돌아간다.

 

4) 3)의 반복문이 모두 수행된 뒤 n 값이 0이라면, 이는 모든 설탕을 포장 완료했다는 것을 뜻한다. 

따라서 이 경우에는, 최종적으로 연산 완료된 cnt의 값을 출력한다.

다만 n 값이 0이 아니라면, 이는 포장되지 못한 설탕이 남아있다는 것을 뜻한다.

이 경우에는, cnt의 값이 아닌 -1을 출력한다.

 

5) 위에서 출력을 완료하였다면, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 2839번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);
	
	int n;
	cin >> n;

	int cnt = 0;
	while (n >= 3) {
		if (n % 5 == 0) { 
			cnt += n / 5;	n = 0;	break;
		}
		n -= 3;	cnt += 1;
	}
	if (n == 0) { cout << cnt << endl; }
	else { cout << -1 << endl; }
}

 

제출 결과

(2022.04.08 백준 2839번 문제 제출 결과)