2979번: 트럭 주차

문제

상근이는 트럭을 3대 가지고 있으며, 트럭을 주차장에 주차할 때 대수에 따라 주차 요금이 할인됩니다.

• 트럭을 1대 주차할 때는 1분에 한 대당 A원을 냅니다.
• 트럭을 2대 주차할 때는 1분에 한 대당 B원을 냅니다.
• 트럭을 3대 주차할 때는 1분에 한 대당 C원을 냅니다.

A, B, C와 3대의 트럭이 주차장에 도착한 시간과 떠난 시간이 주어졌을 때, 상근이가 내야 하는 주차 요금의 총합을 구하는 문제입니다.

• 입력:
  • 첫째 줄에 주차 요금 A, B, C가 주어집니다. (1 ≤ C ≤ B ≤ A ≤ 100)
  • 다음 세 개의 줄에는 각 트럭이 주차장에 도착한 시간과 떠난 시간이 주어집니다. (시간은 1부터 100 사이의 정수)
• 출력: 상근이가 내야 하는 주차 요금

링크: https://www.acmicpc.net/problem/2979

풀이

이 문제는 주어지는 시간의 범위가 1부터 100까지로 매우 작기 때문에, 크기가 101인 배열을 선언하여 각 분(minute)마다 주차된 트럭의 대수를 누적하는 방식으로 쉽게 풀 수 있습니다.

1. 요금 배열 저장: 1대, 2대, 3대일 때의 한 대당 요금을 fee 배열에 차례대로 저장합니다.
2. 시간대별 주차 대수 누적: 각 트럭의 도착 시간(s)부터 떠난 시간(e) 전까지 반복문을 돌며 cnt 배열의 값을 1씩 증가시킵니다.
   • 주의할 점은 트럭이 떠난 시간(e)에는 주차장에 트럭이 없는 것이므로, j < e 로 설정하여 떠난 시간 직전까지만 카운트해야 합니다.
3. 최종 요금 계산: 시간 배열을 1부터 100까지 순회하며 해당 시간에 주차된 트럭이 있다면(cnt[i] > 0), 요금을 계산해 정답에 더해줍니다.
   • 이때 계산식은 주차된 트럭 수 * 한 대당 요금이 되므로, cnt[i] * fee[cnt[i] - 1] 한 줄로 아주 깔끔하게 처리할 수 있습니다.

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       StringTokenizer st = new StringTokenizer(br.readLine());
       
       // 1대, 2대, 3대 주차 시 한 대당 요금 배열 (A, B, C)
       int[] fee = new int[3];
       for (int i = 0; i < 3; i++) {
          fee[i] = Integer.parseInt(st.nextToken());
       }

       // 시간대별 주차된 트럭의 대수를 기록할 배열 (시간 범위 1~100)
       int cnt[] = new int[101];
       
       // 3대의 트럭에 대해 주차 시간 기록
       for (int i = 0; i < 3; i++) {
          st = new StringTokenizer(br.readLine());
          int s = Integer.parseInt(st.nextToken());
          int e = Integer.parseInt(st.nextToken());
          
          // 도착 시간부터 떠난 시간 직전(e-1)까지만 카운트 증가
          for (int j = s; j < e; j++) {
             cnt[j]++;
          }
       }

       int ans = 0;
       
       // 1분부터 100분까지 순회하며 요금 정산
       for (int i = 0; i <= 100; i++) {
          if (cnt[i] == 0) continue;
          
          // 총 요금 += (해당 시간의 트럭 대수) * (해당 대수의 1대당 주차 요금)
          ans += cnt[i] * fee[cnt[i] - 1];
       }

       bw.write(ans + "");

       bw.flush();
    }
}

알고리즘 분류

구현 (Implementation), 시뮬레이션 (Simulation)