[백준] 6064 - 카잉 달력

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

6064번: 카잉 달력

문제 한줄 이해

-카잉 제국에서는 해를 계산할때 이번 해<1(왼쪽):1(오른쪽)> 다음 해<2:2> 이와 같이 1씩 증가시킨다. (단, 이번 해에서 1씩 증가시킬때 왼쪽의 값이 M보다 작으면 +1을 그렇지 않으면 1로 리셋해준다.오른쪽도 동일한 규칙을 가지고 N이 기준)

 

생각난 풀이

1번째 방법: while 반복문을 통해 단순히 1씩 증가시키고 조건에 걸리면 1로 리셋해주는 방법으로 했다.

import sys
t = int(sys.stdin.readline())
for i in range(t):
    m, n, x, y = map(int,sys.stdin.readline().split())

    left, right = 0, 0
    cnt = 0
    while True:
        # 1씩 증가
        left += 1
        right += 1
        # 첫해... 두번째 해 ...
        cnt +=1
        # 끝까지 갔는데 <x:y>를 못찾았다는건 해당되는 해가 없다는 뜻
        if left == m+1 and right == n+1:
            print(-1)
            break
        # 발견하면 스톱!
        if left == x and right == y:
            print(cnt)
            break
        # 해당 조건에 맞으면 리셋
        if left >=m :
            left = 0
        if right >=n:
            right =0

결과는 시간초과... 그래서 간단한 예제를 생각해 연산이 얼마나 일어나는지 파악했다.

10 9 10 9를 예를 들면 1:1 2:2 3:3 4:4 5:5 6:6 7:7 8:8 9:9 10:1  

                                   1:2 2:3 3:4 4:5 5:6 6:7 7:8 8:9 9:1 10:2

                                                               ....

경우의 수가 9*10의 경우의 수가 생기고 40000 39999이라면 40000*39999번의 연산이 발생해 시간 초과가 생기는 것이라 생각했다.

 

2번째 방법: 여러가지 예제를 직접 경우의 수를 나열하면서 마지막 해가 M,N의 최소공배수번째 라는 것 까지는 알아냈다. 그럼 다음 규칙을 찾으려고 노력해봤다.(한시간이나 걸렸다 ...)

우선 문제에서 주어진 x나 y를 둘중 하나를 기준으로 잡는다.

우선 큰틀은 1:1 2:2 3:3 4:4 5:5 ...i:i 계속 증가하는 상황에서 일때 i번째의 해의 결과는 i%m : i%n인 것이다. 

예제에서 10 12 3 9 일때 11번째 모양은 (11%10)1:(11%12)11

그렇다면 어떻게 접근하는게 좋을까 고민했을때

x나 y 중 둘중에 하나를 기준으로 잡고 처음 k 를 x번째라고 하고 원하는 x y가 나올때까지  k에 (x라면 M y라면 N) 을 더해 가는 것이다.

import sys
t = int(sys.stdin.readline())
for i in range(t):
    m, n, x, y = map(int,sys.stdin.readline().split())
    # x를 기준
    k = x
    
    while k<= m*n:
        # 만약에 m이 10이고 x 가 10인 경우에 해를 계산할때 0이 아니라 10이 그대로 나와야하기때문에
        # 아래와 같이 처리
        if x == m or y == n:
            if x == m:
                x = 0
            if y == n:
                y = 0
        if k % m == x and k % n == y:
            break
        else:
            k += m
    if k > m*n:
        k = -1
    print(k)