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

백준의 도로와 신호등(2980) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 본 문제는 길을 가면서 신호등의 상태에 맞게 기다리거나 통과하면서 길을 다 통과하는데 몇초의 시간이 걸리는지 구하는

   문제이다.

   시뮬레이션 문제로서, 문제의 조건에 맞게 구현을 해야 한다. 그렇다면 이 문제에서 우리가 주의해야할 조건부터 알아보자.

   1. 신호등이 빨강색일 때는 신호등이 바뀔 때 까지 기다려야 한다.

   2. 신호등이 초록색일 때는 지나 갈 수 있다.

  

2) 입력으로 각 신호등 마다, 빨간불일 때의 지속시간과 초록불일 때의 지속시간이 주어진다.

   그렇다면 현재시간을 알고 있을 때, 해당 신호등이 빨간불인지 초록불인지 어떻게 구할지 부터 생각해보자.

   예를 들어 1번 신호등이 빨간불 지속시간이 2초, 초록불 지속시간이 2초이고, 현재 시간은 1초인 상황을 생각해보자.

   당연히 1번 신호등은 빨간불일 것이다. 현재시간이 3초가 되어야 초록불로 바뀌게 될 것이다.

   그렇다면, 5초, 10초, 15초, 100초일 때 신호등이 무슨 불인지 생각해보자.

   5초일 때는 빨간불일 것이다. 나머지 10초, 15초, 100초... 그 이상은 계산이 점점 복잡해진다. 잘 모르겠다.

   본인은 이 관계를 구하기 위해서 신호등의 주기 값을 구했다. 여기서 말하는 주기라는 것은

   신호등이 빨간불에서 시작해서 초록불로 바뀌고 다시 빨간불로 되기까지의 시간을 의미한다.

   위에서 말한 빨간불 지속시간 = 2초, 초록불 지속시간 = 2초 인 신호등의 경우 주기는 4초가 된다.

   그렇다면 10초는 무슨불일까? 빨간불일 것이다. 왠지는 모르겠는데 주기를 알고 나니까 계산이 좀 더 쉬워진 것 같다.

  

   본인은 해당 신호등의 현재 상태를 해당 신호등의 주기와 현재 시간을 통해서 구해보았다.

   결론은 "현재시간 % 해당 신호등의 주기 <= 해당 신호등의 빨간불 지속시간" 이라면 신호등은 빨간불 그게 아니라면

   초록불이라는 결론을 찾았다.

   위의 식이 맞는지 한번 검토해보자.

   - 빨간불 지속시간 = 2초

   - 초록불 지속시간 = 2초

   - 현재시간 = 1초 / 5초 / 11초 / 30초

   위의 3가지 값을 가지고 계산해보겠다.

   말한대로라면, 위의 신호등의 주기 = 4초가 된다. 그리고 이 시간들을 위에서 말한 공식에 넣어보자.

   현재시간 1초 % 해당 신호등의 주기 4초 <= 해당 신호등의 빨간불 지속시간 2초

   → 1 % 4 <= 2 가 맞으므로 신호등은 빨간불일 것이다.

   5초로 가보자. 5 % 4 <= 2  → 1 <= 2 이므로 빨간불일 것이다.

   11초로 가보자. 11 % 4 <= 2 → 3 <= 2 이므로 성립하지 않는다. 즉 초록불일 것이다.

   맞는지 확인해보자.

   1, 2초 = R / 3, 4초 = G / 5, 6초 = R / 7, 8초 = G / 9, 10초 = R / 11, 12초 = G

   하나하나 다 해보면 초록불이 맞다는 결론이 나온다.

3) 이제 신호등의 상태를 구하는 건 다했다. 사실상 문제를 거의 다 풀었다고 봐도 무방하다.

   이제 이 부분을 어떻게 구현할지에 대해서 알아보자.

   1. 무한루프를 돌리면서 현재의 거리와 시간을 계속해서 증가시켜준다.

      → 반복문이 한번 끝낫다. = 1초가 증가하였다.

   2. 현재 거리가 신호등이 있는 거리라면 2)에서 알아낸 풀이법을 통해서 초록불인지 빨간불인지 판단한다.

      → 만약에 초록불이라면 그대로 지나갈 수 있으니, 거리 시간을 증가시키고 다시 반복문 실행.

      → 만약에 빨간불이라면, 시간을 초록불이 될 때까지 한번에 증가시킨다.

         → 예를 들어서 1초일 때 빨간불인 신호등에 걸렸다고 생각해보자. 이 신호등은 3초에 초록불로 바뀌게 된다.

            이런 경우에는 2초를 거치고 3초로 갈 필요가 없다. 어차피 2초에도 빨간불이라서 기다려야 하기 때문이다.

            즉, 현재시간을 1초 → 3초로 바로 증가시켜 버리고 신호등을 통과하도록 구현한다.

   3. 현재 거리가 전체 거리와 똑같다면 반복문을 종료시키고 시간을 출력시킨다.

[ 소스코드 ]

#include<iostream>
#include<vector>
 
#define endl "\n"
using namespace std;
 
typedef struct
{
    int D;
    int R;
    int G;
    int Cycle;
}Signal_Lamp;
 
int N, L;
vector<Signal_Lamp> V;
 
void Input()
{
    cin >> N >> L;
    for (int i = 0; i < N; i++)
    {
        Signal_Lamp S;
        int D, R, G;
        cin >> D >> R >> G;
        S.D = D;
        S.R = R;
        S.G = G;
        S.Cycle = S.R + S.G;
        V.push_back(S);
    }
}
 
bool Traffic_State(int Idx, int T)
{
    if (T % V[Idx].Cycle <= V[Idx].R) return false;
    return true;
}
 
void Solution()
{
    int Distance = 0;
    int Time = 0;
    int Idx = 0;
 
    while (1)
    {
        if (Distance == L) break;
        if (Idx < V.size())
        {
            if (V[Idx].D == Distance)    // 신호등에 도착하는 시간이면
            {
                if (Traffic_State(Idx, Time) == true)    // 현재 신호등이 초록불이라면??
                {
                    Distance++;
                    Time++;
                }
                else                // 빨간불이라면
                {
                    int Tmp = Time % (V[Idx].Cycle);
                    Time = Time + V[Idx].R - Tmp;
                }
                Idx++;
                continue;
            }
        }        
        Distance++;
        Time++;
    }
    cout << Time << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}