[백준] 6064.cpp : 카잉 달력

www.acmicpc.net/problem/6064

6064번: 카잉 달력

#include <iostream>
using namespace std;

int t;
int M, N, x, y;

// 최대 공약수, 유클리드 호제법
int gcd(int a, int b)
{
  return b == 0 ? a : gcd(b, a % b);
}

int main(void)
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin >> t;

  for(int i = 0 ; i < t ; i++)
  {
    cin >> M >> N >> x >> y;

    int ans = x;    // X축 고정시켜놓고 그 X축에 있는 Y값들을 비교
    int target = 0; // 해당 X축에 대한 해당 반복 때 비교할 Y값 임시 저장

    // 가능한 최대값은 가로 세로의 최소공배수
    int max = M * N / gcd(M, N);
    // 나머지 연산자를 사용할 경우 0~N-1 까지 나오기 때문에 N은 0으로 바꿔준다
    if(y == N) y = 0;

    for(int j = 0 ; j < N  ; j++)
    {
      // Y값은 N 으로 나눈 나머지
      target = ans % N;
      // 이번에 돌아올 Y 값이 내가 구하려는 y값과 같다면 반복 끝!
      if(target == y) break;
      // 다음턴에 돌아올 y 값을 판별하기 위해 M 만큼 증가
      ans += M;
      // 만약 가능한 최대값이 넘어갔을 경우 불가능한 경우라 판단
      if(ans > max)
      {
        ans = -1;
        break;
      }
    }
    cout << ans << '\n';
  }
}

 

[Try]

1. 입력값과 같을때까지 완전탐색 비슷하게 시켜버리기? 예상대로 시간초과가 나버렸다 ㅋㅋ

2. 특정 x 위치(혹은 y 위치) 에서의 반대쪽 값은 나머지 연산자로 구할 수 있다는 특징을 이용

3. 로직 꼼꼼히 확인 할 것

4. 최대값이 넘어가는지에 대한 검사를 반복문에서 계속 해주는게 안전한 것 같다. 반복 횟수도 신경써줄것

 

[Point]

1. 로직을 생각해내지 못해서 인터넷을 참고하였다. 로직 자체도 함정들이 조금 껴있어서 계속 틀림. 정확한 파악이 필요

 

[More]

1. 중국인의 나머지 정리 (CRT 알고리즘)