BOJ 5612 - 터널의 입구와 출구

문제

BOJ 5612 - 터널의 입구와 출구

터널을 통과하는 차량 흐름을 시뮬레이션하는 문제다. 초기 터널 내 차량 수 M에서 매 시간마다 입구로 A대가 들어오고 출구로 B대가 나간다. 도중에 차량이 0 미만이 되면 즉시 0을 출력하고, 그렇지 않으면 전체 시간 중 최대 차량 수를 출력한다.

입력

• 첫 줄에 시간 수 N과 초기 차량 수 M이 주어진다.
• 이후 N줄에 걸쳐 각 시간의 입구 차량 수 A와 출구 차량 수 B가 주어진다.

출력

• 시뮬레이션 중 최대 차량 수를 출력한다. 차량 수가 음수가 되면 0을 출력한다.

예제

풀이

초기값을 최댓값으로 두고, 매 시간마다 차량 수를 갱신하며 최댓값을 추적한다.

1. N과 M을 입력받고, tmp = M으로 최댓값 초기화
2. 각 시간마다 m = m + a - b로 현재 차량 수 갱신
3. m < 0이 되면 tmp = 0으로 설정 후 즉시 종료
4. 그렇지 않으면 m >= tmp일 때 최댓값 갱신
5. 반복 종료 후 tmp 출력

핵심 아이디어: 초기 차량 수도 최댓값 후보이므로 tmp = M으로 초기화하고, 음수 발생 시 즉시 0을 반환한다.

코드

#include <iostream>
using namespace std;
int main()
{
  int n, m;
 
  cin >> n >> m;
  int a, b;
  int tmp = m;
  for (int i = 0; i < n; i++)
  {
    cin >> a >> b;
    m = m + a - b;
    if (m < 0)
    {
      tmp = 0;
      break;
    }
    if (m >= tmp)
      tmp = m;
  }
  cout << tmp;
}

복잡도

• 시간: O(N) — N개의 시간 단계를 한 번 순회
• 공간: O(1) — 상수 개의 변수만 사용