본문 바로가기
자료구조와 알고리즘/알고리즘

트럭 주차

by oncerun 2023. 7. 1.
반응형

 

문제를 해석해 보자.

 

트럭을 총 세 대 가지고 있고, 한 대 주차 시 분당 A원, 두 대 주차 시 분당 B원, 세 대 주차 시 분당 C원이다.

 

세 대의 트럭이 고유한 도착 시간과 떠난 시간을 가지고 있다. 

 

트럭이 겹치는 구간에 적용할 비용과 그렇지 않고 독자적으로 주차했을 때 비용들을 구해 합쳐야 한다. 

 

입력의 시간은 1과 100 사이다.

 

이를 어떻게 효율적으로 저장하고 계산하는 알고리즘을 만들 수 있을까?

 

 

 

1. 주차한 트럭 수만큼 적용될 비용을 저장해야 한다.

 

분당 요금을 계산하는 과정에서 지속적으로 호출될 가능성이 높다.

이를 체크하고 몇 대면 얼마를 특정 요금을 나타내는 자료구조에 추가하도록 해야 하지 않을까? 

 

 

2. 분당 요금을 계산하는 경우 해당 시간에 몇 대가 주차되었는지 확인하고 요금을 부과해야 한다.

 

1에서 100까지의 시간을 두고 각 트럭의 도착 시간과 떠난 시간을 체크하여 각 배열의 인덱스를 시간으로 치환하고 몇 대가 있는지 저장해 보는 건 어떨까?

 

#include <bits/stdc++.h>

using namespace std;

int cost[3];
int carCountsPerMinute[100];

int main() {

    int result = 0;
    vector<tuple<int, int>> parking;

    for(int & i : cost) cin >> i;

    for(int i=0; i<3; i++){
        int arrivalTime, departureTime;
        cin >> arrivalTime >> departureTime;
        parking.emplace_back(arrivalTime, departureTime);
    }

    for (const auto& input : parking){
        auto [first, second] = input;
        for(int i=first; i<second; i++){
            carCountsPerMinute[i]++;
        }
    }

    for (int carCount : carCountsPerMinute)
        if (carCount == 1) {
            result += cost[0];
        } else if (carCount == 2) {
            result += cost[1] * 2;
        } else if (carCount == 3) {
            result += cost[2] * 3;
        }

    cout << result;

    return 0;
}

 

고민은 다음과 같았다 1분~6분인 경우 범위를 어떻게 잡아줘야 할까?

이상 미만으로 잡아주는 게 좋다고 한다. 

 

이유를 모르겠어서 gpt를 활용해 봤다.

 

범위를 "이상"과 "미만"으로 잡는 것은 일반적으로 컴퓨터 과학에서 인덱싱과 범위 표현에 흔히 사용되는 관례입니다. 이러한 관례는 다음과 같은 이유로 좋은 선택입니다:

1. 일관성: 다른 프로그래머들이 일반적으로 "이상"과 "미만"을 사용하므로, 코드를 읽는 사람들이 즉시 이해할 수 있습니다. 이 관례를 따른다면 코드를 작성하고 읽는 데 일관성이 있습니다.

2. 오류 방지: "이상"과 "미만"을 사용하면 범위의 시작과 끝을 명확하게 구분할 수 있습니다. 만약 "이하"와 "초과"를 사용한다면 혼란스러워질 수 있고, 잘못된 범위를 설정할 위험이 높아집니다.

3. 표준 라이브러리와의 호환성: 많은 표준 라이브러리 및 알고리즘은 "이상"과 "미만" 관례를 따르며, 예를 들어 벡터나 배열의 인덱싱, 반복자의 범위 등을 다룰 때 이 관례를 사용합니다. 이러한 표준 라이브러리와의 호환성을 유지하기 위해 "이상"과 "미만"을 사용하는 것이 좋습니다.

 

참고.

강의 코드는 tuple, vector를 사용하지 않고 입력 이후 즉시 반복문을 통해 카운팅을 한 이후

요금을 계산하는 로직을 실행했다.

반응형

'자료구조와 알고리즘 > 알고리즘' 카테고리의 다른 글

농구 경기(1159)  (0) 2023.07.02
Palindrome  (0) 2023.07.02
문자열 카운팅.  (0) 2023.07.01
2309  (0) 2023.06.26
prefix sum  (0) 2023.06.25

댓글