개발 블로그

문제 링크 : www.acmicpc.net/problem/1476

문제

준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다.

지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19)

우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다.

예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 되면 16 16 16이 아니라 1 16 16이 된다. 이유는 1 ≤ E ≤ 15 라서 범위를 넘어가기 때문이다.

E, S, M이 주어졌고, 1년이 준규가 사는 나라에서 1 1 1일때, 준규가 사는 나라에서 E S M이 우리가 알고 있는 연도로 몇 년인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 수 E, S, M이 주어진다. 문제에 나와있는 범위를 지키는 입력만 주어진다.

출력

첫째 줄에 E S M으로 표시되는 가장 빠른 연도를 출력한다. 1 1 1은 항상 1이기 때문에, 정답이 음수가 나오는 경우는 없다.

접근 방법 1

num을 1부터 하나씩 증가시키면서 나머지가 각각 입력값 e, s, m 과 일치하는지 비교했는데 시간초과가 떴다.

#include <iostream>

using namespace std;


int main(){
    
    
    
    int e,s,m;
    cin >> e >> s >> m;
    
    int num= 1;
    while(1){
        
        if(num%15 == e && num%28 == s && num%19 == m){
            break;
        }
        else num++;
        
    }
    
    cout << num << endl;
    
    return 0;
}

접근 방법 2

num을 1부터 증가시키는 것이 아니라 28의 배수를 기준으로 증가시키면서, num을 15와 19로 나눈 나머지를 입력값과 비교했다. 28의 배수로 한 이유는 15와 19보다 28이 크기 때문에 계산량을 줄이기 위함이다. 그러나 또 시간 초과가 떴다.

#include <iostream>

using namespace std;


int main(){
    
    
    
    int e,s,m;
    cin >> e >> s >> m;
    
    int num, q = 0;
  
    while(1){
        
        num = 28*q + s;
        if(num%15 != e || num%19 !=m){
            q++;
        }
        else{
            break;
        }
        
        
    }
    
    
    cout << num << "\n";
    
    return 0;
}

1,2번 시간초과 난 이유

참고:www.acmicpc.net/board/view/51295

입력이 15,28,19 일때를 생각해보자. 즉 e = 15, s = 28, m = 19일때 (num%15)의 범위는 0~14이므로 절대로 15(e)가 될 수 없다. 마찬가지로 (num%19)의 범위는 0~18이므로 절대로 19(m)이 될 수 없어서 계속 반복문을 도는 것이다.

그래서 아래와 같이 28의 배수를 기준으로 할 때, 반복문 시작 전에 if 문으로 e와 m을 체크해주면 시간초과가 뜨지 않는다. 이때 주의할 점은 s에 대해서 검사하면 아예 틀린 값이 나온다. (이유 : 입력이 15, 28, 19이면 출력이 0이 나온다!)

#include <iostream>

using namespace std;


int main(){

    int e,s,m;
    cin >> e >> s >> m;
    
    if(e>=15) e = e%15;
    if(m>=19) m = m%19;
    
    int num, q = 0;
  
    while(1){
        
        num = 28*q + s;
        if(num%15 != e || num%19 !=m){
            q++;
        }
        else{
            break;
        }
    }
    
    cout << num << "\n";
    
    return 0;
}

접근 방법 3

num을 1부터 하나씩 증가시키면서 num - e를 15로 나눈 값이 0인지를 판단하고, s와 m에 대해서도 같은 방법으로 비교하여 3조건이 모두 0이면 반복문을 멈춘다.

예를 들어,

num = 5266, e = 1, s = 2, m = 3 일 때,

5266 = 15*351 + 1

5266 = 28*188 + 2

5266 = 19*277 + 3 

이므로 각 나머지를 LHS로 이항해서 15,28,19 로 나눈 나머지가 모두 0일 때 반복문을 멈춘다.

위의 방법과 어떤 점에서 다른지 모르겠지만 아래 방법은 시간초과가 나지 않았다. 

#include <iostream>

using namespace std;


int main(){
    
    
    
    int e,s,m;
    cin >> e >> s >> m;
    
    int num = 1;
  
    while(1){
        
        if((num-e)%15 == 0 && (num-s)%28==0 && (num-m)%19 == 0){
            break;
        }
        else num++;
        
    }
    
    
    cout << num << "\n";
    
    return 0;
}