본문 바로가기

알고리즘 관련/BOJ

BOJ)6064 카잉 달력

문제: icpc.me/6064


n년도를 x:y로 표현할 때 n+1년도는 if(x==m) x=1 else x=x+1 if(y==n) y=1 else y=y+1 로 표현할 때 x:y가 몇년도인지 찾는 문제이다.


처음에 단순하게 시뮬레이션을 돌려봤으나 시간초과를 받아서 문제를 다시 보니 M과 N이 40000씩이므로 O(N*M)의 시뮬레이션으로는 해결할 수 없는 문제였다.


그래서 수식을 사용하여 for(int i=0;i<=n;i++) (m*i+(x-y)) 가 n으로 나누어 떨어질 때 m*i+x 가 답이된다.


이때 원래 세상의 종말이 온다는 마지막 해 이후에는 정의되지 않으므로 m과 n의 LCM 까지만 돌리면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <cstdio>
#include <algorithm>
#define INF 987654321
using namespace std;
int t, m, n, x, y, r, a;
int main() {
    scanf("%d"&t);
    while (t--) {
        scanf("%d%d%d%d"&m, &n, &x, &y);
        r = INF;
        for (int i = 0; i <= n; i++) {
            if (!((m*+ (x - y)) % n)) {
                r = m*+ x;
                break;
            }
        }
        for (int i = 0; i <= n; i++) {
            if (!((m*+ (m - n)) % n)) {
                a = m*+ m;
                break;
            }
        }
        if (r == INF || a < r)
            printf("-1\n");
        else
            printf("%d\n", r);
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)5430 AC  (0) 2017.02.21
BOJ)1966 프린터 큐  (0) 2017.02.21
BOJ)2787 흔한 수열 문제  (0) 2017.02.20
BOJ)2191 들쥐의 탈출  (0) 2017.02.20
BOJ)9169 나는 9999번 문제를 풀 수 있다  (0) 2017.02.20