숫자를 세야한다 -> 카운팅 배열을 활용

우선 숫자를 세야한다. 동시간에 몇대가 겹치는지를 확인해야하니까.

• 숫자,문자를 세는 경우 -> 카운팅 배열을 활용한다.

1분 단위의 시작점을 인덱스로 활용

입력에 차량의 입차가 1분, 출차가 6분이라고한다.

->1분 단위의 시작점을 인덱스로 활용한다.
-> 입차 1분, 출차 6분이면 인덱스 1,2,3,4,5를 1증가시키는 식으로 카운팅 배열을 구현한다.

풀이

#include <bits/stdc++.h>

using namespace std;

int cnt[100]={};
int cost[4]={};

int main() {
    int begin;
    int end;
    int sum=0;
    for(int i=0;i<3;i++) cin >> cost[i+1]; // O(1)
    for(int i=0;i<3;i++) { //O(1)
        cin >> begin >> end; 
        for(int j=begin; j<end; j++) cnt[j]++;
    }
    
    for(int i=1;i<100;i++) { O(1)
        switch(cnt[i]) {
            case 1: sum+=cost[1]*cnt[i];
                break;
            case 2: sum+=cost[2]*cnt[i];
                break;
            case 3: sum+=cost[3]*cnt[i];
                break;
            default:
                break;
        } 
    }
    cout << sum;
    return 0;
}

위와 같이 풀면된다. 시간복잡도는 O(1) 이다.

배운 점

• 숫자,문자를 세야한다 -> 카운팅 배열을 활용
• 문자열을 세야한다 -> map 활용
• 1분 단위의 시작점을 인덱스로 활용

위 2가지를 꼭 기억해두자.

특히 범위가 중요한 문제의 경우 항상 카운팅 배열의 인덱스화가 필요할때 뭔가 애매했는데 앞으로는 기준 단위의 시작점을 인덱스로 활용하는 방법으로 fix 하는게 편리할것같다.