코드.kr

BOJ 10269 - Train Passengers

6 min read

문제 링크

문제 요약

주어진 기차의 운행 기록이 일관성이 있는지 검증하는 문제입니다. 기차의 총 정원 C와 n개의 역에 대한 정보(out_cnt: 하차 승객 수, in_cnt: 승차 승객 수, wait_cnt: 대기 승객 수)가 주어집니다. 이 기록이 다음 조건들을 모두 만족하면 “possible”을, 그렇지 않으면 “impossible”을 출력해야 합니다.

  1. 열차에 탑승한 승객 수가 0 미만이거나 총 정원 C를 초과해서는 안 됩니다.
  2. 열차가 만석이 아님에도 불구하고 대기 승객이 있어서는 안 됩니다. (즉, 빈자리가 있는데 대기 승객이 있는 경우는 불가능합니다.)
  3. 열차는 여정을 시작할 때와 끝낼 때 모두 비어있어야 합니다.
  4. 마지막 역에서는 대기 승객이 없어야 합니다.

풀이

이 문제는 주어진 조건을 바탕으로 기차의 승객 수를 시뮬레이션하면서 각 시점마다 조건 위반이 없는지 검사하는 방식으로 해결할 수 있습니다.

핵심 아이디어: 기차의 현재 승객 수를 나타내는 변수 current를 0으로 초기화하고, 각 역마다 발생하는 승객 변화와 관련된 조건을 순차적으로 확인합니다.

풀이 과정:

  1. 초기 상태 설정:

    • 기차는 여정을 시작할 때 비어있어야 하므로, 현재 승객 수를 나타내는 current 변수를 0으로 초기화합니다.

  2. 각 역마다 시뮬레이션 및 검증:

    • n개의 역을 순서대로 방문하며 다음 조건들을 검사합니다.
    • 하차 승객 처리:
      • current에서 out_cnt만큼 승객을 내립니다.
      • 검증 1 (승객 수 0 미만 방지): 만약 current가 out_cnt보다 작아 승객이 음수가 되려 한다면, 이는 불가능한 상황이므로 즉시 “impossible”을 반환합니다.
      • current -= out_cnt 연산을 수행합니다.
    • 승차 승객 처리:
      • current에 in_cnt만큼 승객을 태웁니다.
      • 검증 2 (정원 초과 방지): 만약 current에 in_cnt를 더한 값이 C를 초과한다면, 이는 불가능한 상황이므로 즉시 “impossible”을 반환합니다.
      • current += in_cnt 연산을 수행합니다.
    • 대기 승객 처리 및 검증:
      • 검증 3 (빈자리 있는데 대기 승객 방지): 만약 현재 current가 C보다 작아 기차에 빈자리가 있음에도 불구하고 wait_cnt가 0보다 크다면 (즉, 대기 승객이 있다면), 이는 불가능한 상황이므로 즉시 “impossible”을 반환합니다.
    • 마지막 역 대기 승객 검증:
      • 검증 4 (마지막 역 대기 승객 방지): 현재 처리 중인 역이 마지막 역(i == n - 1)인데 wait_cnt가 0보다 크다면, 이는 불가능한 상황이므로 즉시 “impossible”을 반환합니다.

  3. 여정 종료 후 검증:

    • 모든 역에 대한 처리가 끝난 후, 기차가 여정을 마칠 때 비어있어야 합니다.
    • 검증 5 (여정 종료 후 빈 기차): 만약 최종 current 값이 0보다 크다면, 기차가 비어있지 않은 상태로 종료된 것이므로 즉시 “impossible”을 반환합니다.

  4. “possible” 반환:

    • 위의 모든 검증 단계를 통과했다면, 주어진 기록은 일관성이 있다는 뜻이므로 “possible”을 반환합니다.

정답 코드

def solve():
  current = 0
 
  C, n = map(int, input().split())
 
  for i in range(n):
    out_cnt, in_cnt, wait_cnt = map(int, input().split())
 
    # 1. 하차 승객이 현재 승객보다 많으면 안됨 (승객 수가 0 미만으로 떨어지는 경우)
    if current < out_cnt:
      return False
    
    current -= out_cnt
 
    # 2. 승차 후 총 정원 C를 초과하면 안됨
    if current + in_cnt > C:
      return False
    
    current += in_cnt
 
    # 3. 열차에 빈자리가 있는데 대기 승객이 있으면 안됨
    # 즉, current < C (빈자리 있음) 이고 wait_cnt > 0 (대기 승객 있음) 이면 안됨
    if current < C and wait_cnt > 0:
      return False
    
    # 4. 마지막 역에서는 대기 승객이 없어야 함
    if i == n - 1 and wait_cnt > 0:
      return False  
  
  # 5. 모든 역을 거친 후, 기차는 비어있어야 함
  if current > 0:
    return False
 
  return True
 
 
if __name__ == "__main__":
  tc = 1
  for t in range(1, tc+1):
    ret = solve()
 
    print("possible" if ret else "impossible")

연관 페이지

참고 문헌 / 사이트

그래프 뷰