190712_카잉 달력_C

- 백준 > 카잉달력 

 

보통 2시간 지나도록 안풀리면 해답을 찾는데, 카잉 달력은 C로 푼 답을 찾기도 쉽지 않아 결국 풀어버렸다...

시간 복잡도 해결하느라 9번이나 삽질을 했다.

처음 1번은 문제를 제대로 이해하지 못해서 틀렸고, 다음 5번은 메인 함수에서 시간 복잡도를 해결하지 못해 틀렸고, 

그 다음 1번은 실수로("\n"을 빼먹음), 그 다음 1번은 실수를 바로 잡고 최소 공배수 함수에서 시간 복잡도를 해결해서 맞았다.

8번은 메인 함수에서 틀리고, 1번은 최소 공배수 구하는 함수에서 시간 복잡도를 줄이는 방식(유클리드 호제법으로 변경)으로 해결했다. 

 

아래는  C로 작성한 카잉 달력의 답이다. 

#include <stdio.h>

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

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

int main(void) {
    int count;
    scanf("%d", &count);

    for ( int i=0; i<count; i++ ) {
        int m, n, x, y;
        scanf("%d %d %d %d", &m, &n, &x, &y);
        long long endgame = lcm(m, n); 

        long long loop = 0;
        long long result = 0;
        while ( 1 ) {
            long long temp = (m*loop) + x;
            if ( temp > endgame ) {
                result = -1;
                break;
            }
            if ( (temp % n == y) || (temp % n == 0 && n == y ) ) {
                result = temp;
                break;
            }
            loop++;
        }
        printf("%lld\n", result);
   }

    return 0;
}

 

# 풀이 과정