2학기 7주차_알고리즘( 백준2839번 : 설탕배달)

 

 

▶ 문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

▶ 입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

▶ 출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

 

 

📌 내풀이

 

 

▶ 첫번째 풀이

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
    int N, result;
    int sug_5, sug_3;

    scanf("%d", &N);

    sug_5 = N / 5;
    sug_3 = N % 5 / 3;

    result = sug_5 + sug_3;

    if (N % 15 != 0) {
        result = -1;
    }

    printf("%d", result);
    return 0;
}

 

우선 문제를 봤을 때, 15배수 일때와 아닐때로 구분을 해야겠다라고 생각했는데, N이 깔끔하게 5와 3으로 나누어지지 않으면 -1로 출력해야하기때문이다. 

그리고 그 기준 외에는 5로 크게 한번 나누고 그 나머지만큼을 3으로 나눈 몫에 맞아 떨어진다면 그만큼이 최소일 수 밖에 없을 것이라고 생각했다.

 

그래서 짠 첫번째 코드가 위의 코드이다.

 

 

 

 

첫번째 코드가 틀렸는데 뭐 다른이유가 있을수도 있지만 내가 한가지 뚜렷하게 놓친부분이 15의 배수로 -1을 출력하게 한것이다. 생각해보니까 그보다 작은 수인데 3과 5로 안나뉘는 것도 있다. 

너무 단순하게 생각했으니 그부분의 논리를 일단 수정해줬다.

 

#include <stdio.h>

int main() {
    int N, result;
    int sug_5, sug_3;

    scanf("%d", &N);

    sug_5 = N / 5;      // 5킬로그램 봉지
    sug_3 = N % 5 / 3;  // 3킬로그램 봉지

    result = sug_5 + sug_3;  // 총 봉지 

    if (N % 3 != 0 && N % 5 != 0) {
        result = -1;
    }

    printf("%d", result);
    return 0;
}

 

 

 

-1이 출력되는 범위를 수정해주었는데도 틀렸다고 결과가 뜬다. 아무래도 내눈에 보이지 않는 논리상 문제가 있는 것 같은데,  수정할 부분에 대해 도움을 받았다.

 

#include <stdio.h>

int main(void)
{
    int N = 0, A = 0, B = 0, i = 0;
    
    scanf("%d", &N);
    if(N % 5 == 0)
    {
        printf("%d", N / 5);
        return 0;
    }
    if(N % 3 == 0) A = N / 3;
    
    for(i = N / 5; i > 0; i--)
    {
        if((N - 5 * i) % 3 == 0)
        {
            B = (N - 5 * i) / 3 + i;
            break;
        }
    }
    if(A == 0 && B == 0)
    {
        printf("-1");
        return 0;
    }
    
    if(B == 0) printf("%d", A);
    else printf("%d", B);
    return 0;  
}

 

 

문제를 풀다가 시간초과 문제까지 발생해서 공부하며 찾아본 코드와 내가 짠 코드의 차이점에 대해 고민해봤다.

 

일단 반복문과 조건문을 쓰는 구간이 훨씬 많았다.

사실 내가 코드를 짤 때 , 간결하고 알아보기 쉽게 짜는 것도 코드를 잘짜는 거니까 라고 생각하면서 .. 음 이렇게 간단하게 짤 순 없을텐데 반복문 안쓰는게 찝찝했다.

 

일단 N이 3의 배수인지 검사를 한번 거치고 , A값을 대입한다.

그리고 for문을 통해 5의 몫 크기부터 0보다 클때까지 i가 작아지면서 검사를 하는데 , 만약에 N에서 5를 뺀값에 i를 곱해준 값이 3의 배수일 경우 B에 값을 대입하도록 한다.

그리고 만약에 그 A와 B값이 둘다 0일 경우에는 -1을 출력하도록하고 있다.

 

 

일단 내가 부족했던 부분은 결국은 최소를 출력해야하기때문에 반복문을 통해서 가장 최소인 값을 구하고 탈출하도록 구문을 짜지 않았다는 부분인 것 같았다.

 

 

 

일단은 문제 자체가 접근하는 것도 로직을 짜는 것도 엄청 복잡한 것은 아니었는데, 너무 간단하게 풀려했던 것은 아닌가 반성을 했고, 다양한 방법으로 풀이를 해보면 좋은 점을 다시한번 느낄 수 있는 문제였다.

 

 

[ 참고 학습 자료 ]

 

 

백준 알고리즘 2839번: 설탕 배달 C언어 (tistory.com)

백준 알고리즘 2839번: 설탕 배달 C언어