[백준 알고리즘 2839번 문제] 설탕배달 (C언어) #실버Ⅳ

실버Ⅳ

 

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

2839번: 설탕 배달

 

 

 

 

풀이 방법

 

먼저 5kg 봉지를 최대한 많이 선택한 후 나머지 무게를 3kg 봉지로 채우는 것이 최적해를 찾는 방법이다.

 

1. 먼저 5kg 봉지의 최대개수와 5kg으로 나누었을때 남은 나머지 무게를 구한다.

2. 3kg 봉지로 나머지 무게를 나눈 나머지가 0이 될때까지 5kg 봉지를 한개씩 빼본다.

3. 5kg 봉지가 0개일때 나머지 무게가 3kg 봉지로 나누어 떨어지지 않는다면 -1을 출력한다.

 

내 코드

#pragma warning(disable:4996)
#include <stdio.h>
 
int main() {
 
    int n, cnt, temp;
 
    scanf("%d", &n);
 
    cnt = n / 5;
    temp = n % 5;
 
    while (cnt >= 0) {
        if (temp % 3 == 0) {
            cnt = cnt + temp / 3;
            printf("%d\n", cnt);
            return 0;
        }
        cnt--;
        temp += 5;
    }
 
    printf("-1\n");
        
 
    return 0;
}

 

느낀점

이 문제의 경우 5kg 봉지를 먼저 최대한 많이 사용한 후, 5kg 봉지를 하나씩 줄여가며 남은 무게가 3kg의 배수인지를 확인하는 것이 핵심이었다.