[C] 백준 2839번 : 설탕 배달

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

2839번: 설탕 배달

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
    int x, y, i = 0,size = 0;
    int N;
    int sum[1000] = {0};
    scanf("%d",&N);
    for (int x = 0; x <= 1000; x++) {
        for (int  y = 0; y < 1667; y++) {
            if (5 * x + 3 * y == N) {
                sum[i] = x + y;
                i++;
                size = i;
            }
        }
    }
    if (sum[0] == 0) { printf("-1"); }
    else {
        int min = sum[0];
        for (int i = 1; i < size; i++) {
            if (sum[i] < min) { min = sum[i]; }
        }
        printf("%d",min);
    }
 
    return 0;
}

문제에서 요구한 것은

1. 5든 3이든 나눴을 때 나머지가 반드시 0이어야한다.

2.나눴을 때의 몫의 합이 최솟값이야한다.

18이라는 숫자가 N으로 주어졌다면

3으로 6번 나눠떨어지게 할 수 있지만 5로 3번 3으로 1번 나눠 4번으로 최솟값을 얻을 수 있다.

 

보자마자 떠오른 것은 방정식이다.

5x+3y가 N이 될때의 x+y의 최솟값을 구하기

문제에서 N의 범위는 3이상 5000이하였기 때문에X는 1000이하 Y는 1667미만으로 반복문의 범위를 설정할 수 있었다.

 

다시 5x+3y = N을 충족시키는 x와 y의 값의 합이 최솟값일 때를 구해야하는데 바로 판별할 수 없으므로

우선 x와 y의 값의 합을 보관할 수 있는 정수형 배열을 선언하였다.

배열의 크기를 처음에 100으로 선언하였는데런타임 에러(OutofBounds)가 뜬 것을 보아

방정식의 해의 경우의 수가 100개 넘을 수 있다고 인지하고 1000으로 선언하였는데 맞았다.

사실 정확히 모르겠다. 혹시나 보게되신다면 알려주실 분이 계시면 정말 감사하겠습니다.

 

그 다음은 흔히 아는 최솟값 구하듯이 반복문을 구성해주면 되는데

13번째 줄에 size변수를 정의함으로써 몫의 합 중 최솟값을 판별할 때의 반복문의 범위를 설정해줄 수 있다.

만약 17같이 방정식의 해가 존재하지 않는다면 sum배열의 0번째 원소는 0일 것이고

최솟값 판별할 필요 없이 바로 -1을 출력해주면 된다.