[baekjoon] 백준 6063번 : 카잉 달력 (by python 파이썬) 자세한 설명

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

6064번: 카잉 달력

 

정답 code

#카잉 달력

t = int(input())

for _ in range(t):
    m,n,x,y = map(int,input().split())
    f = 1
    while x <= m*n:
        if (x-y)%n == 0:
            print(x)
            f = 0
            break
        x += m
    
    if f:
        print(-1)

 

solution

나에게 상당히 까다로운 문제였다.

처음엔 그냥 처음부터 1씩 올리면서 찾았는데 당연히 시간초과가 발생했다.

규칙을 찾기가 상당히 어려워 구글링의 힘을 빌려 여러 블로그를 참고했다.

처음에 한두개 설명을 봐도 이해가 잘 되지 않았다.. 

 

핵심은 x에 m을 더하던 y에 n을 더하던 해당 값은 고정된다는 것이다. (m =10 n = 12인 경우 10진법 12진법이라고 생각하면 편하다)

 

ex) x를 움직이는 경우

입력

m, n = 10, 12  // x, y = 3, 9

case

year = k (m이상 x에서 괄호값)을 뜻한다

1year - <1,1>

2y - <2,2>

3y - <3,3>

4y - <4,4>

5y - <5,5>

6y - <6,6>

7y - <7,7>

8y - <8,8>

9y - <9,9>

10y - <10,10>

11y - <1(11),11>

12y - <2(12),12>

13y - <3(13),1>

14y - <4(14),2>

15y - <5(15),3>

 

위와 같이 k 값은 변환하지되지 않은 x값이다 

규칙은 (k - y) % n = 0 이된다

 

k대신 x를 변환시키지 않은값 을 대입해 식을 완성할 수 있다.

x에 m을 더하면 계속 해당 수를 유지 함으로 m을 더해가며 k경우에 y값이 맞는지 확인하면된다.

k= 3  -> (3-9) % 12 != 0

k = 13 -> (13-9) % 12 != 0

k = 23 -> (23-9) % 12 != 0

k = 33 -> (33-9) % 12 == 0 

정답은 33 이 나오게 된다.

x = 3(33) y = 9

 

이렇게하면 하나씩 찾지 않고 m만큼 지나면서 찾으면서 시간을 단축시킬 수 있다.