[알고리즘 문제 풀기] Transporting Spaghetti(24750)

1. 문제 풀이 아이디어

• 최소한의 트럭 개수를 기준으로 시작하여, 조건을 만족하는 보트 개수가 정수일 때까지 증가시키며 탐색한다.

• 트럭 적재량 a, 보트 적재량 b, 최소 필요량 d, 트럭 최소량 c가 주어졌을 때, 트럭 * a - d가 b로 나누어떨어지는지 확인하며 정수 해를 찾는다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int[] input = Array.ConvertAll(sr.ReadLine().Trim().Split(), int.Parse);
    int a = input[0];
    int b = input[1];
    int c = input[2];
    int d = input[3];
    int g = gcd(a, b);
    if (d % g != 0)
    {
        sw.WriteLine("No solution.");
        return;
    }
    int truck = (d + c + a - 1) / a;

    int max = b / g;
    int count = 0;
    while (((truck * a - d) % b) != 0 && count < max)
    {
        truck++;
        count++;
    }
    if (count >= max)
    {
        sw.WriteLine("No solution.");
        return;
    }
    int boat = (truck * a - d) / b;
    sw.WriteLine($"We need {truck} truck{(truck != 1 ? "s" : "")} and {boat} boat{(boat != 1 ? "s" : "")}.");
}

int gcd(int a, int b)
{
    while (b != 0)
    {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

3. 정리

• gcd(a, b)가 d를 나누지 못하면 해가 존재하지 않으므로 바로 종료한다.

• 트럭 개수 = (d + c + a - 1) / a로 계산하여 c만큼 실을 수 있는 최소 트럭 수를 구한다.

• 트럭 적재 총량에서 d를 뺀 값이 b로 나누어떨어지는지 확인하며 반복한다.

• 이 반복은 (b / gcd(a, b))번 이상 하면 주기를 벗어나므로 그 전에 해를 찾지 못하면 종료한다.

• 트럭 개수를 구하면 남은 양으로 보트 개수를 구하고 출력한다.

• 출력 시 단수/복수 표현을 함께 고려한다. (0은 복수다.)