[C++] 백준 2980 - 도로와 신호등

문제 - 도로와 신호등 (Silver4)

[백준 2980] https://www.acmicpc.net/problem/2980

풀이 전략

그림을 그려서 관계를 확인하고, 여러 조건문으로 구해보고자 했다.

풀이

그림을 보면 일단 처음과 제일 마지막은 신호등의 영향을 받지 않기 때문에 따로 더해주고, 신호등의 영향을 받는 신호등과 신호등 사이의 시간이 중요하다.
처음부터 시작해서 신호등은 계속 R,G값에 따라 바뀌고 있기 때문에 신호등에 도달했을 때까지의 시간과 대기시간을 고려해서 문제를 풀어야 한다.
예제대로 하면 빨간색 동그라미를 더한 값이 정답이 된다.

현재 이동시간%신호등의 주기(R+B)가 빨간불이 지속되는 시간보다 짧거나 같으면 신호등이 빨간불이고, 그 반대는 파란불이라는 규칙을 찾을 수 있어서 이를 바탕으로 구현을 했다.

소스 코드

/* 
# Question: BJ 2980 (https://www.acmicpc.net/problem/2980)
# Rank : Silver4
# Algorithm : Math, Implementation, Simulation
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N,L;
    cin>>N>>L;

    vector<vector<int>> A(N,vector<int>(3));
    vector<int> Dist(N+1);
    for(int i=0;i<N;i++){
        cin>>A[i][0]>>A[i][1]>>A[i][2];
    }

    // 신호등 사이의 거리 계산
    for(int i=0;i<=N;i++){
        if(i==0){
            Dist[i]=A[i][0];
        }else if(i==N){
            Dist[i]=L-A[i-1][0];
        }else{
            Dist[i]=A[i][0]-A[i-1][0];
        }
    }

    int total=0;
    for(int i=0;i<N;i++){
        int cycle=A[i][1]+A[i][2]; // 빨간불 + 파란불 주기
        total+=Dist[i]; // 신호등까지 이동시간
        if(A[i][1]>=(total%cycle)){
            total+=(A[i][1]-(total%cycle)); // 빨간불을 기다리는 시간
        }
    }
    total+=Dist[N]; // 마지막 신호등 없는 거리 더해주기
    cout<<total<<'\n';
    return 0;
}

결과