Pr.2979 트럭주차

Pr.2979 트럭주차

문제

상근이는 트럭을 총 세 대 가지고 있다. 오늘은 트럭을 주차하는데 비용이 얼마나 필요한지 알아보려고 한다.</br> 상근이가 이용하는 주차장은 주차하는 트럭의 수에 따라서 주차 요금을 할인해 준다.</br> 트럭을 한 대 주차할 때는 1분에 한 대당 A원을 내야 한다. 두 대를 주차할 때는 1분에 한 대당 B원, 세 대를 주차할 때는 1분에 한 대당 C원을 내야 한다.</br> A, B, C가 주어지고, 상근이의 트럭이 주차장에 주차된 시간이 주어졌을 때, 주차 요금으로 얼마를 내야 하는지 구하는 프로그램을 작성하시오.</br>

입력

첫째 줄에 문제에서 설명한 주차 요금 A, B, C가 주어진다. (1 ≤ C ≤ B ≤ A ≤ 100)</br> 다음 세 개 줄에는 두 정수가 주어진다. 이 정수는 상근이가 가지고 있는 트럭이 주차장에 도착한 시간과 주차장에서 떠난 시간이다. 도착한 시간은 항상 떠난 시간보다 앞선다. 입력으로 주어지는 시간은 1과 100사이 이다.

출력

첫째 줄에 상근이가 내야하는 주차 요금을 출력한다.

예제 입력

5 3 1
1 6
3 5
2 8

예제 출력

33

풀이과정

전제조건

1. 시간 복잡도, 공간 복잡도
   • 트럭 수는 3으로 고정,
   • 1번의 for 문으로 문제 해결 가능
2. 최대, 최소 조건
   • 주차 시간의 t는 최소0, 최대 100
3. 사용 알고리즘
   • 단순 구현으로 해결가능

     1~100 배열을 돌면서 해당 시간에 주차된 트럭수 카운트 최종적으로 배열의 수 * 주차요금

4. 반례

제출 코드

#include<bits/stdc++.h>
using namespace std;

int a,b,c,sum;
int truck[3][2];
int parking[101];

int main(){
    cin >> a >> b >> c;
    for (int i = 0; i < 3; i++){
        cin >> truck[i][0] >> truck[i][1];
    }

    for (int i = 1; i <= 100; i++){
        for (int j = 0; j < 3; j++){
            if (truck[j][0] <= i && i < truck[j][1]){
                parking[i]++;
            }
        }
    }

    for(int i = 0; i <= 100; i++){
        if (parking[i] == 1){
            sum += a;
        }
        else if (parking[i] == 2){
            sum += b * 2;
        }
        else if (parking[i] == 3){
            sum += c * 3;
        }
    }
    cout << sum;
    return 0;
}

해설

생각해볼 점

• 주차 시간을 입력 받을 때 배열을 카운트 -> 공간복잡도를 낮출 수 있음
• 시간은 이상 미만이다. for(int j = a; j < b; j++)

수정방안

• 주차 시간을 입력 받을 때 배열을 카운트
• counting은 map 또는 arr로 접근한다.

  for(int i = 0; i < 3; i++){
		cin >> a >> b; 
		for(int j = a; j < b; j++)cnt[j]++;
	}

정답 코드

#include <bits/stdc++.h>
using namespace std;   
int A, B, C, a, b, cnt[104], ret;
int main(){
	cin >> A >> B >> C; 
	for(int i = 0; i < 3; i++){
		cin >> a >> b; 
		for(int j = a; j < b; j++)cnt[j]++;
	}
	for(int j = 1; j < 100; j++){
		if(cnt[j]){
			if(cnt[j] == 1) ret += A;
			else if(cnt[j] == 2)ret += B * 2;
			else if(cnt[j] == 3)ret += C * 3;
		}
	}
	cout << ret << "\n"; 
    return 0;
}