JArchive 프로그래밍 일기

문제

카잉달력 백준 6064번

리뷰

ㅠㅠ 풀고 해설보며 이해하는 데 오래걸린 문제다.

x는 M 주기로 돌아가고, y는 N 주기로 돌아간다.

그러니까 답 i = i % M == x 가 된다. 또한 i % N == y 를 만족해야 한다.

그래서 i를 찾는 for문을 M 크기로 증가시키는 것이다.

i는 x로 시작한다.

종말 날짜 endday는 M과 N의 최소공배수다. 이것은 gcd 함수로 계산할 수 있다.

아래 코드를 보자.

while(T--){ // 테스트 케이스 만큼 반복 

        cin >> M >> N >> x >> y;

        int i = x; // x로 시작 
         int endday = lcm(M, N);
        int result = -1; // 실패할 경우 답의 base case

        for(i = x; i <= endday; i += M){ // x는 M만큼 건너뛴다 

            ...
        }

        cout << result << '\n';
    }

이제 for문 안에서는 y를 찾아야 한다.

y는 N과 똑같을 수도 있고, 아닐 수도 있다.

가장 쉬운 케이스는 i가 N으로 나눈 나머지가 y 인 경우다. 바로 정답이 되고 i 를 출력하면 된다.

y == N 인 경우, 그 순간의 i 가 N으로 나누어 떨어지는 숫자인지 확인해야 한다.

for(i = x; i <= endday; i += M){ // x는 M만큼 건너뛴다 

    // i를 N 으로 나눈 나머지가 y 이라면 만족 
    // y == N 인 경우에는, i 가 N으로 나누어 떨어져야 만족 
    if( (y == N && i % N == 0 ) || (i % N == y) ){ 
        result = i; 
        break;
    }
}

코드

#include <iostream>
#include <algorithm>
using namespace std;

// 카잉달력

int T, M, N, x, y;

int gcd(int a, int b){ // 최대공약수

    while(b != 0){
        int t = a % b;
        a = b;
        b = t;
    } 

    return a;
} 

int lcm(int a, int b){ // 최소공배수 
    return (a * b) / gcd(a,b);
}

int main(void){

    cin >> T;

    while(T--){

        cin >> M >> N >> x >> y;

        int i = x; // x로 시작 
         int endday = lcm(M, N);
        int result = -1; // 실패할 경우 답의 base case

        for(i = x; i <= endday; i += M){ // x는 M만큼 건너뛴다 

            // i를 N 으로 나눈 나머지가 y 이라면 만족 
            // y == N 인 경우에는, i 가 N으로 나누어 떨어져야 만족 
            if( (y == N && i % N == 0 ) || (i % N == y) ){ 
                result = i; 
                break;
            }

        }

        cout << result << '\n';
    }

    return 0;    
}

반례

백준 질문게시판 - jh05013님의 반례 및 FAQ

그 외 참고 해설

15
40000 39999 39999 39998
40000 39999 40000 39999
40000 40000 40000 39999
40000 39998 40000 39997
39999 2 39998 2
3 40000 3 39999
40000 3 40000 3
8 2 4 2
10 12 2 12
12 10 12 10
12 10 1 1
12 6 12 6
10 1 5 1
1 10 1 5
1 1 1 1

// 답 
1599959999
1599960000
-1
-1
39998
39999
120000
4
12
60
1
12
5
5
1