[1일 1알고] 노란불 신호등

어제 문제는 풀었는데 포스팅을 안했었네요

 

https://school.programmers.co.kr/learn/courses/30/lessons/468371

프로그래머스

여러 신호등이 각자의 주기에 따라 초록불, 노란불, 빨간불이 번갈아 점등하고 있는 상황입니다.

문제의 답은 모든 신호등이 동시에 노란불인 가장 빠른 시각을 찾는 것입니다.

 

이런 상황이면 항상 제한사항을 먼저 보게됩니다.

signals = 신호등의 개수는 5이하입니다.

그리고 G, Y, R 은 각각 1보다 크고 18보다 작으며 합치면 20보다 작습니다.

 

결론적으로 문제의 답은 각 신호등의 주기의 최대 공약수를 넘지 않을 것이고, 더 간단하게 생각하면 20^5는 절대 넘을 수 없습니다.

따라서 매초 각 신호등의 색을 얻어 비교하더라도 시간초과가 일어나지 않을 것임을 알 수 있습니다.

---

#include <string>
#include <vector>

using namespace std;

enum Color
{
    G = 0,
    Y = 1,
    R = 2,
};

Color GetColor(vector<int>& signal, int sec)
{
    int total = signal[0] + signal[1] + signal[2];
    int cur = sec % total;

    if (cur < signal[0])
        return Color::G;
    else if (cur < signal[0] + signal[1])
        return Color::Y;
    else
        return Color::R;
}

int solution(vector<vector<int>> signals) {
    long long MAX = 20 * 20 * 20 * 20 * 20;

    int answer = -1;
    for (int i = 0; i < MAX; ++i)
    {
        bool flag = true;
        for (vector<int>& signal : signals)
        {
           if (GetColor(signal, i) != Color::Y)
           {
               flag = false;
               break;
           }
        }
        if (flag)
        {
            answer = i + 1;
            break;
        }
    }
    return answer;
}

 

더 시간을 줄이고 싶다면 MAX를 최대공약수를 구해서 사용하면 되겠네요

 

그리고 정답은 1index를 사용하기 때문에 저처럼 0index를 통해 계산했다면 변환이 필요할 것입니다.