99클럽 코테 스터디 18일차 TIL [04/23]

[시작]

참여 기간 : 2025/03/31 ~ 2025/04/28

참여 난이도 : 파이썬 / 비기너

본 글에서 다룬 문제 : 백준 1590번_캠프가는 영식

과정이 끝나도 나는 혼자 달릴 예정

solved.ac

노동요들으면서 풀었음. 역시 노래 들으면서 해야지

 

 

 

 

[오늘의 문제]

 

[문제 해석]

꼬아서 낸 문제는 아니어서 해석은 쉽다.

영식이가 T시에 정류장에 도착했고

버스는 총 N대 있으며

각 버스는 S(첫 출발 시각), I(간격), C(총 몇 번 출발)의 정보를 가짐

우리가 구해야 하는 것은 영식이가 기다리지 않고 가장 빨리 탈 수 있는 버스는 언제인지

그 대기 시간을 구하는 것

못 타면 -1 출력

 

 

 

[구현]

선형 탐색으로 먼저 도전

문제의 입력이 크긴 한데..

제한시간을 초과할 정도는 아닐 것 같아서 해봤다.

단순 조회 + 조건 체크로 코드 구성

최소 대기시간 = -1

N, T 입력받기

N번 반복:
    S, I, C 입력받기

    C번 반복 (j from 0 to C-1):
        출발시간 = S + I * j

        만약 출발시간 >= T라면:
            대기시간 = 출발시간 - T
            최소 대기시간 갱신
            반복 종료 (break)

출력: 최소 대기시간

 

 

 

[코드]

# N = 버스 대수, T = 영식 도착시간
# S = 버스 처음 출발 시간, I = 다음 버스 출발까지 간격, C = 총 몇 번 출발하는지
import sys
input = sys.stdin.readline

N, T = map(int, input().split())
min_wait = -1  # 탈 수 있는 버스 중 기다리는 시간이 가장 짧은 값. 처음엔 못 찾은 상태로 시작

for _ in range(N):
    S, I, C = map(int, input().split())

    for j in range(C):
        time = S + I * j
        if time >= T:
            wait = time - T
            if min_wait == -1 or wait < min_wait:
                min_wait = wait
            break  # 더 확인할 필요 없으니 break

print(min_wait)

시간복잡도 : O(N × C)

참고로 버스 1대당 탐색은 O(C)

C번 전부 확인해야 하므로 이진 탐색보다는 느림. (당연히)

 

 

 

[제출 결과]

 

 

 

[이진탐색으로 풀어보기]

사실 이진탐색으로 풀면 시간은 단축되는데 코드 구현이 귀찮다.

그렇치만 경험치를 쌓으려면 해야 한다.

바로 ㄱㄱ

최소 대기시간 = -1

N, T 입력받기

N번 반복:
    S, I, C 입력받기

    left = 0, right = C-1
    후보 출발시간 = -1

    이진탐색 while left <= right:
        mid = (left + right) // 2
        출발시간 = S + I * mid

        만약 출발시간 >= T:
            후보 출발시간 = 출발시간
            오른쪽 줄이기 (right = mid - 1)
        아니면:
            왼쪽 늘리기 (left = mid + 1)

    후보 출발시간이 존재하면:
        대기시간 = 후보 출발시간 - T
        최소 대기시간 갱신

출력: 최소 대기시간

대충 이런 느낌으로 구현하면 될 것 같다.

 

import sys
input = sys.stdin.readline

N, T = map(int, input().split())
min_wait = -1  # 기다릴 수 없으면 -1 유지

for _ in range(N):
    S, I, C = map(int, input().split())

    # 이진 탐색: j는 출발 횟수의 인덱스
    left, right = 0, C - 1
    answer_time = -1

    while left <= right:
        mid = (left + right) // 2
        time = S + I * mid  # mid번째 출발 시각

        if time >= T:
            answer_time = time      # 후보 저장
            right = mid - 1         # 더 이른 출발 시각이 있는지 왼쪽 탐색
        else:
            left = mid + 1          # 더 늦게 출발하는 쪽으로 이동

    # 탈 수 있는 버스를 찾았다면 대기 시간 계산
    if answer_time != -1:
        wait = answer_time - T
        if min_wait == -1 or wait < min_wait:
            min_wait = wait

print(min_wait)

사실 이진 탐색 문제는 접근 방법이 비슷해서

며칠 동안 풀었던 문제와 구현만 조금씩 다르지 유사한 것 같다.

그런데 로컬에서 코드 작성하고 테스트하면 몇 번 틀리고 다시 수정해야 성공한다 ㅎㅎ;

 

백준에서 제출 결과 시간은 차이가 없는데

시간복잡도는 O(log C)이다.

C가 커져도 빠른 게 특징(이진탐색)

 

 

 

[회고]

이제 코드를 잘 작성해서 문제를 맞히려면

문제 해석이 어렵지 않아야 한다고 느낀다.

사실 수학 능력도 중요하지만 백준 브론즈 실버에서는 독해 능력이 더 중요하지 않나...

가끔 피곤한 상태로 문제를 풀려고 하면 머리가 굳어서 말하는 감자가 되어버려 해석을 못한다 ㅎ...

암튼 이진탐색은 어떻게 구현하는지 숙지했으니 계속 경험치 쌓아가면 될 것 같다.