BOJ 2979 - 트럭 주차

문제

3대의 트럭 주차 시간과 동시 주차 대수별 분당 요금(A, B, C)이 주어질 때, 총 주차 요금을 구하라.

입력

첫째 줄에 1대일 때 요금 A, 2대일 때 B, 3대일 때 C, 이후 3줄에 각 트럭의 도착/출발 시간이 주어진다.

출력

총 주차 요금을 출력한다.

예제

입력	출력
`5 3 1` `1 6` `3 5` `2 8`	`33`

풀이

시간 배열로 각 시각별 주차 대수를 카운팅한 뒤, 대수별 요금을 적용한다.

크기 101의 시간 배열을 만들고, 각 트럭의 주차 구간에 1씩 누적한다
배열을 순회하며 각 시각의 동시 주차 대수를 확인한다
1대면 1*A, 2대면 2*B, 3대면 3*C를 누적한다
총 요금을 출력한다

핵심 아이디어: 구간 카운팅으로 각 시각의 동시 주차 대수를 구하면, 시간대별로 올바른 요금을 O(T)에 적용할 수 있다 (T: 최대 시간).

코드

#include <bits/stdc++.h>
using namespace std;
int a, b, c, ans = 0;
int t[101];
int main()
{
  cin >> a >> b >> c;
  for (int i = 0; i < 3; i++)
  {
    int s, e;
    cin >> s >> e;
    for (int j = s; j < e; j++)
      t[j]++;
  }
  for (int i = 1; i <= 100; i++)
  {
    if (t[i] == 1)
      ans += t[i] * a;
    else if (t[i] == 2)
      ans += t[i] * b;
    else
      ans += t[i] * c;
  }
  cout << ans << '\n';
}

복잡도

시간: O(1) (최대 시간 범위 100 고정)
공간: O(1)

문제