[알고리즘] 2979번: 트럭 주차

0. 문제

2979번: 트럭 주차

 

문제

상근이는 트럭을 총 세 대 가지고 있다. 오늘은 트럭을 주차하는데 비용이 얼마나 필요한지 알아보려고 한다.

상근이가 이용하는 주차장은 주차하는 트럭의 수에 따라서 주차 요금을 할인해 준다.

트럭을 한 대 주차할 때는 1분에 한 대당 A원을 내야 한다. 두 대를 주차할 때는 1분에 한 대당 B원, 세 대를 주차할 때는 1분에 한 대당 C원을 내야 한다.

A, B, C가 주어지고, 상근이의 트럭이 주차장에 주차된 시간이 주어졌을 때, 주차 요금으로 얼마를 내야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문제에서 설명한 주차 요금 A, B, C가 주어진다. (1 ≤ C ≤ B ≤ A ≤ 100)

다음 세 개 줄에는 두 정수가 주어진다. 이 정수는 상근이가 가지고 있는 트럭이 주차장에 도착한 시간과 주차장에서 떠난 시간이다. 도착한 시간은 항상 떠난 시간보다 앞선다. 입력으로 주어지는 시간은 1과 100 사이이다.

출력

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

예제 입력 1

5 3 1
1 6
3 5
2 8

예제 출력 1

33

예제 입력 2

10 8 6
15 30
25 50
70 80

예제 출력 2

480

 

---

1. 문제 이해

 

예제 입력 1

5 3 1
1 6
3 5
2 8

예제 출력 1

33

 

어떻게 33원이 나올 수 있는지 이해해 보았다.

 

1	2	3	4	5	6	7	8	합계
a	a	a	a	a
		b	b
	c	c	c	c	c	c
5	6	3	3	6	5	5		33

 

예제 입력 1은 배열로 풀기에 적합하지만 예제 입력 2는 배열로 풀기가 어렵다.

 

만약 배열로 풀려면 배열의 크기가 아주 커야 한다.

 

그렇기 때문에 배열보다는 map으로 푸는 것이 더 합리적이다.

 

---

2. 제출

 

1. A, B, C를 저장한다.
2. pair의 배열을 사용해서 트럭의 도착 시간과 떠난 시간을 저장한다.
3. map을 사용해서 시간당 트럭을 수를 계산한다.
4. 지불해야 하는 요금의 총합을 계산해서 출력한다.

 

//백준 2979번: 트럭 주차
#include <iostream>
#include <map>

using namespace std;

map<int, int> mp;
int A,B,C;
pair<int, int> truck[3];
int sum;

int main(){
    cin >> A >> B >> C;
    for(int i=0; i<3; i++){
        cin >> truck[i].first >> truck[i].second;
    }
    for(int i=0; i<3; i++){
        for(int j=truck[i].first; j<truck[i].second; j++){
            auto it = mp.find(j);
            if(it == mp.end()){
                mp.insert(make_pair(j,1));
            }else{
                (*it).second += 1;
            }
        }
    }
    for(pair<int, int> i : mp){
        switch(i.second)
        {
            case 1:
                sum += A;
                break;
            case 2:
                sum += 2*B;
                break;
            case 3:
                sum += 3*C;
                break;
        }
        //cout << i.first << ":" << i.second << " : " << sum << "\n";
    }
    /*
    cout << "A,B,C" << A << B << C << "\n";
    for(pair<int, int> i : truck){
        cout << i.first << i.second << "\n";
    }
    for(pair<int, int> i : mp){
        cout << i.first << ':' << i.second << '\n';
    }
    */
    cout << sum << "\n";
    return 0;
}

 

---

개선

 

위에서는 배열 대신에 map을 사용했다.

 

하지만 주어진 문제에서 “주어지는 시간은 1과 100 사이이다.”라고 언급을 했다.

 

그렇기 때문에 복잡하게 map으로 구현하기보다는 100의 사이즈를 가지는 배열로 처리해도 된다.

 

//백준 2979번: 트럭 주차
#include <iostream>

using namespace std;

int A, B, C, a, b, cnt[104], sum;
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) sum += A;
            else if(cnt[j] == 2) sum += 2*B;
            else if(cnt[j] == 3) sum += 3*C;
        }
    }
    cout << sum << "\n";
    return 0;
}

 

훨씬 쉽게 풀 수 있다.

 

---