[BOJ] 백준 2980 도로와 신호등

출처: https://www.acmicpc.net/problem/2980

 Input 

2 10

3 5 5

5 2 2

 

 Output 

12 

 

도로를 지나가면서 신호 상황에 따라 기다리거나 통과하면서 몇 초의 시간이 걸리는지 구하는 문제입니다.

- 빨간불인 경우, 기다려야 한다.

- 초록불인 경우, 그냥 지나 갈 수 있다.

 

각 신호등에 도착했을 때,  빨간불인지 초록불인지 상태를 알 수 있어야 합니다.

신호등은 빨간불 + 초록불 = 1 cycle을 가집니다.

ex) 빨간불 3초, 초록불 1초인 신호등일 때, 10초일 때 상태는

    → 1 cycle = 4초

    → 10 % 4 = 2 ≤ 3 

    →빨간 불

    + if) 11초인 경우 11 % 4 = 3 ≤ 3 이지만 신호가 빨간불에서 초록불로 바뀌는 시점으로 초록불로 간주.

 

Test Case 분석

거리 3 지점에서 빨간불에 걸려 2초 대기시간을 가집니다.

거리 5 지점에서는 초록불로 대기시간 없이 통과합니다.

이동시간 10 + 대기시간 2 = 12초

 

※ [C++] [STL] Map

[C++] [STL] Map

 

map과 구조체를 이용해 map<int, trafficLight>

: 거리 D 지점에 신호등 정보를 저장

---

#include <iostream>
#include <map>
using namespace std;
 
typedef struct{
    int R, G;
    int cycle;
}trafficLight;
 
int N, L;
map<int, trafficLight> trafficMap;
 
bool isGreenLight(trafficLight signal, int elapsedTime){
    // 빨간불 대기시간
    if (signal.R - (elapsedTime % signal.cycle) > 0)
        return false;    
    return true;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> L;
    int D, R, G;
    for (int i = 0; i < N; i++){
        trafficLight signal;
        cin >> D >> R >> G;
        signal.R = R;
        signal.G = G;
        signal.cycle = signal.R + signal.G;
        trafficMap.insert(make_pair(D, signal));
    }
 
    int distance = 0;
    int answer = 0; 
    while (1){
        if (distance == L) 
            break;
        
        // 해당 위치에 신호등이 존재하는 경우
        if(trafficMap.count(distance)){
            trafficLight signal = trafficMap.find(distance)->second;
            if (isGreenLight(signal, answer))  {
                distance++;
                answer++;
            }
            else{
                // 빨간불인 경우, 대기시간만 더해줍니다.
                int temp = answer % (signal.cycle);
                answer += signal.R - temp;
            }        
            continue;
        }
        
        // 거리 증가 및 시간 경과        
        distance++; answer++;
    }
    cout << answer << endl;
}