백준 6064 - 카잉 달력 (c++)

백준 6064 - 카잉 달력

문제 링크

생각과 접근

처음 생각

• 처음 문제에 접근할 때 단순히 문제의 조건대로 1년씩 늘려서 x와 y를 늘려주는 식으로 했다. 역시나 시간 초과. 결국 띄엄띄엄 검사하는 생각해야 했다.

개선한 생각

• 문제의 조건에 의해 <1, 1>이 <m, n>이 되면 카잉 달력은 끝나게 된다. 그렇다면 <m, n>이 되려면 몇 년이 지나야 할까. 결론부터 말하면 m과 n의 최소공배수가 되면 끝난다 . 그 이유는 왼쪽 수가 m이 되는 경우는 카잉년이 m의 배수가 될 때이고, 오른쪽 수가 n이 되는 경우는 카잉년이 n의 배수가 될 때이기 때문이다. 그래서, limit이라는 변수를 선언해서 카잉년을 몇 년까지 검사를 해야할 지 담아 놓았다. 최소공배수를 구하기 위해, 간단히 함수도 구현해 주었다.

    int gcd(int a, int b){
        while(b != 0){
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
  
    int lcm(int a, int b){
        return a * b / gcd(a, b);
    }

• 문제에서 요구하는 것은 _<x, y>는 몇 년째인가?_ 이다. 위와 같이 배수적인 표현으로 생각해보면, 왼쪽 좌표는 카잉년에서 m으로 나눈 나머지 가 되고, 오른쪽 좌표는 카이년에서 n으로 나눈 나머지 가 된다. 숫자를 하나씩 늘려가면서 생각해보면 쉽게 나오는 결론이였다.

  • 현재 카잉년을 tar이라고 했을 때,

    • tar % m = x이고
    • tar % n = y인
      tar는 <x, y>의 카잉년이 된다.
      만일 찾은 카잉년이 limit 이상으로 넘어가게 된다면, 답이 될 수 없다.

  • 위의 조건으로 코드를 구현해보았다.

      cin >> m >> n >> x >> y;
    
      flag = 0;
      limit = lcm(m, n);
    
      for(int j = x; j <= limit ; j += m){
          if(j % n == y % n){
              flag = 1;
              cout << j << endl;
              break;
          }
      }
      if(flag == 0){
          cout << "-1" << endl;
      }

    • for문에서 나타나는 j가 위에서 설명한 tar이 된다. j는 for문을 돌면서 왼쪽 좌표가 x가 되는 케이스 를 찾는다. 그 j에서 오른쪽 좌표가 y가 되는 케이스 를 찾으면 그 값이 출력해야 하는 값이 된다.

코드

#include <bits/stdc++.h>
using namespace std;

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

int lcm(int a, int b){
    return a * b / gcd(a, b);
}

int sit, m, n, x, y, limit, flag;

int main(){
    ios_base::sync_with_stdio(false);

    cin >> sit;
    for(int i = 1; i <= sit; i++){
        cin >> m >> n >> x >> y;

        flag = 0;
        limit = lcm(m, n);

        for(int j = x; j <= limit ; j += m){
            if(j % n == y % n){
                flag = 1;
                cout << j << endl;
                break;
            }
        }
        if(flag == 0){
            cout << "-1" << endl;
        }
    }
}

채점 결과