[백준] 6064번: 카잉달력

가영·2021년 3월 11일
0

알고리즘

목록 보기
30/41
post-thumbnail

문제보기

이 문제는 기본적인 문젠데 너무 삽질을 오래했다.
x를 먼저 찾고, 거기에서 M씩 더해가며 y가 일치하는 연도를 찾으면 빨리 찾을 수 있다!

UB는 M과 N의 최소공배수다. ^_^

#include <stdio.h>
#include <stdlib.h>

int lcm(int a, int b) {
  int r, prod = a*b;
  if (a < b) {
    int tmp = a;
    a = b;
    b = tmp;
  }
  while(b) {
    r = a % b;
    a = b;
    b = r;
  }
  return prod / a;
}

int main() {
  int t;
  scanf("%d", &t);
  while(t--) {
    int M, N, x, y;
    scanf("%d%d%d%d", &M, &N, &x, &y);
    int limit = lcm(M, N);
    int tmpy = x;
    while(tmpy <= limit) {
      if (y%N == tmpy%N)
        break;
      tmpy += M;
    }
    if(tmpy > limit)
      printf("-1\n");
    else printf("%d\n", tmpy);
  }
  return 0;
}

갑자기 c로 푼 이유는 알고리즘 강의 끝나고 바로 풀었기 때문이당 별 이유도 없고 또 쓸 일도 없을 거같다

이 문제가 자료 구조를 쓸 일이 없어서 c로 풀 수 있었던 것 같다.

1개의 댓글

comment-user-thumbnail
2022년 2월 9일

불쌍한 c 언어 가끔씩 켜주세요,,,

답글 달기