[백준] 1590 - 캠프가는 영식

1. 문제

1590번: 캠프가는 영식

2. 개요

영식이는 캠프장에 가기 위해 버스를 타려 한다.

N대의 버스와 각 버스의 운행 시작 시간, 운행 간격, 운행 대수가 주어진다.

영식이가 정류장에 T분에 도착했다. 이 때, 버스를 타기 위해 기다려야하는 최소 시간을 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

각 버스의 정보마다 이분탐색을 진행해 답을 구한다.

버스는 첫 운행 버스를 0번으로 생각한다. 0을 시작값, 마지막 버스 번호를 최종값으로 잡는다.

이를 토대로 버스의 출발시각과 영식이의 정류장 도착 시각의 차이를 이용해 답을 갱신해나간다.

모든 버스에 대해 이분탐색을 마친 후, 답을 확인한다.

만약 답이 초기값과 똑같다면 탈 버스가 없다는 얘기이므로 -1을 출력하고 갱신되었다면 그대로 출력한다.

3-2. Python

import sys

N, T = map(int, sys.stdin.readline().split())

answer = sys.maxsize

for i in range(N):
    S, I, C = map(int, sys.stdin.readline().split())

    start, end = 0, C - 1

    while start <= end:
        mid = (start + end) // 2

        if T == S + I * mid:
            answer = 0
            break

        elif T > S + I * mid:
            start = mid + 1

        else:
            answer = min(answer, S + I * mid - T)
            end = mid - 1

if answer == sys.maxsize:
    print(-1)

else:
    print(answer)

3-3. C#

namespace boj_1590
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            string[] input = sr.ReadLine().Split();

            int N = int.Parse(input[0]);
            int T = int.Parse(input[1]);

            int answer = int.MaxValue;

            for (int i = 0; i < N; i++)
            {
                input = sr.ReadLine().Split();
                int S = int.Parse(input[0]);
                int I = int.Parse(input[1]);
                int C = int.Parse(input[2]);

                int start = 0;
                int end = C - 1;

                while (start <= end)
                {
                    int mid = (start + end) / 2;

                    if (T == S + I * mid)
                    {
                        answer = 0;
                        break;
                    }

                    else if (T > S + I * mid)
                        start = mid + 1;

                    else
                    {
                        answer = (int)MathF.Min(answer, S + I * mid - T);
                        end = mid - 1;
                    }
                }
            }

            if (answer == int.MaxValue)
                sw.WriteLine(-1);

            else
                sw.WriteLine(answer);

            sw.Close();
        }
    }
}