GCD, LCM

문제

프로그래머스 노란불 신호등

설명

처음 봤을 때 반복문을 돌리면 되겠는데? 라는 생각으로 접근했지만, 종료 시점에 대한 의문이 들어 결국 풀지 못 함

필요 알고리즘

• GCD( 최대공약수): 유클리드호제법!

long long gcd(long long a, long long b){
 while(b!=0){
long long r = a%b;
a=b;
b=r;
}
return a;
}

• LCM(최소공배수): 두 자연수의 곱 / 최대공약수

풀이

#include <string>
#include <vector>
#include <numeric>

using namespace std;

long long gcd_ll(long long a, long long b){
    while(b){
        long long r=a%b;
        a=b;
        b=r;
    }
    return a;
    
}

long long lcm_ll(long long a,long long b){
    return a/gec_ll(a,b) * b;
}

int solution(vector<vector<int>> signals) {
    long long limit=1;
    
    for(auto s: signals){
        int G = s[0];
        int Y = s[1];
        int R = s[2];
        
        # 각 신호등의 주기 구하기 -> 주기들의 최소공배수를 구함 -> 해당 최소공배수가 전체 주기가 됨
        int period = G+Y+R;
        
        # 처음 limit 값은 처음 신호등의 주기가 됨. 이후 각 신호등의 주기와 돌면서 최소 공배수를 구함
        limit = lcm_ll(limit,period);
    }
    
    for(long long t =1; t<=limit;t++){
        bool allYellow  = true;
        
        # 모든 신호등 반복
        for(auto s:signals){
            int G=s[0];
            int Y = s[1];
            int R = s[2];
            
            # 각 신호등의 주기 뽑기
            int period = G+Y+R;
            # 신호등마다의 현재 시점에서 노란색인지 확인을 위함
            int pos = (t-1) % period;
            
            # 노란색 영역에 포함이 안되면 반복문 종료 -> 다음 시점으로
            if(!(G<=pos&&pos < G+Y)){
                allYellow=false;
                break;
            }
        }
        
        # 모든 신호등에서 false가 없다면 노란색 영역에 모든 신호등이 있는 것이므로 통과
        if(allYellow){
            return (int)t;
        }
    }
    
    # 위 조건에서 return이 안나왔다면 노란색 없는거니깐 버려
    return -1;
}