백준 문제풀이 : (6064) 카잉 달력 - Python

문제 : https://www.acmicpc.net/problem/6064

6064번: 카잉 달력

 

시간 제한	메모리 제한	난이도	알고리즘 분류
2초	64 MB	Silver 1	수학 / 정수론

 

 

문제

 

 

풀이

c++로 풀이했을 때는 조금 복잡한 규칙을 만들어서 풀이했었는데, 정답이 잘 나와 다시 고민하지 않고 넘어갔었다. 하지만 파이썬으로 같은 풀이법을 옮겼더니 곧장 시간 초과를 뿜어내더라...

 

그래서 풀이 과정을 다시한번 되짚어보며, 계산이나 반복을 줄일 수 있는 방법을 찾아봤다.

 

문제의 정답을 변수 day라고 정의한다. M과 N, 그리고 x와 y의 관계에 대해 조금만 고민해보면 다음과 같은 규칙을 찾아낼 수 있다. 

• day%M =  x 이고, day%N = y 이다.

그리고 이 규칙은 바로 다음과 같이 바꿔 쓸 수 있다.

• (day-x)%M = 0 이고, (day-y)%N = 0 이다.

위 규칙이 성립할 수 있는 이유는 간단하다. 

 

날짜가 하루 씩 지나갈 때 마다 x와 y의 값은 함께 1씩 증가하고, 각가 M과 N 숫자를 마주쳤을 때 다시 1로 돌아가기 때문이다. 

 

즉, 예를 들어 M, N의 값이 1=5, 4 라면, x와 y 값은 날짜의 흐름에 따라 아래와 같이 변한다는 뜻이다.

 

(day )  x : y

(day1) 1 : 1

(day2) 2 : 2

(day3) 3 : 3

(day4) 4 : 4

(day5) 5 : 1

(day6) 1 : 2

(day7) 2 : 3

(day8) 3 : 4

(day9) 4 : 1 

 

x와 y는 M과 N 단위로 초기화 된다. 그러니 day를 M으로 나눴을 때의 나머지는 항상 x일 수 밖에 없다. (y의 공식도 마찬가지다.)

 

여기까지 알아냈다면 일단 풀이법을 떠올리는 것은 어렵지 않다. 

day를 1씩 증가시키는 for문을 만들어 규칙에 맞는 day값을 찾아내기만 하면 되기 때문이다. 

 

하지만 그렇게 전수조사를 하면 Python은 물론이고 c++에서도 시간초과가 발생한다. 

탐색 시간을 줄일 수 있는 방법을 고민해봐야 한다는 뜻이다. 

 

일반적으로 가장 단순하게 탐색 시간을 줄일 수 있는 방법은, day의 증가값을 더 큰 수로 늘리는 것이다. 이 방법으로 조금 더 고민해보면, day에 대한 규칙을 한 가지 더 발견할 수 있다. 

• day 는 x+M*i 이거나, y+N*j 이다. (i와 j는 각각 x와 y가 초기화 된 횟수다.)

예를 들어 M과 x를 기준으로 생각해 볼 경우, day%M은 무조건 x이기에 day는 x에 M을 더해나가는 수열의 수 중 하나일 수 밖에 없다.

 

이 방법을 통해 day의 초기값을 x와 y 중 하나로 정하고 반복 시의 증가값을 M또는 N으로 늘려보았다. 그랬더니 Python에서도 무사히 성공 판정을 받았다. 

 

M,x와 N,y 중 어떤 규칙을 증가값으로 삼을 지는 M과 N 중 어떤 수가 더 큰 지로 정했다. (조금이라도 증가값을 늘려, 반복을 줄이기 위해...)

 

 

코드 작성

import sys;
input = sys.stdin.readline; 
printt = sys.stdout.write;

T = int(input());
resultF = "";

for t in range(0, T) :
    M, N, x, y = map(int, input().split(' '));
    
    result = -1;
    
    mORn = M if M>N else N; //M과 N중 더 큰 값을 저장
    xORy = x if mORn==M else y; //위에서 M이 선택됐다면 x를, N이 선택됐다면 y를.
    
    if x==y : result=x; //x와 y 값이 같다면 day=x=y 이다. (x와 y는 항상 함께 1씩 증가하고, 두 수가 다시 같아지는 시점은 <M, N>에 도달한 다음 날이기 때문. 
    else : 
        day=xORy; //day의 초기값 지정
        while day<=M*N : 
            if ((day-x)%M==0) and ((day-y)%N==0) : 
                result=day;
                break;
            day+=mORn;
    
    resultF+=(f'{result}\n');

printt(resultF);

 

 

END.