[파이썬] 백준 알고리즘 No.6064 카잉 달력

 

 

백준 6064번 카잉 달력 문제

 

125652, 428

 

 

1번째 풀이 / 메모리 초과

1 <= m , n <= 40000 거의 16억에 가까운 계산을 해야함. 메모리/시간 초과

# 메모리 초과 코드
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    m, n, tx, ty = map(int, input().split())
    year = []
    x, y = 1, 1
    while True:
        year.append((x, y))
        if x == m and y == n:
            break

        x += 1
        y += 1
        if x > m:
            x = 1
        if y > n:
            y = 1


    if (tx, ty) in year:
        ans = year.index((tx, ty)) + 1
        print(ans)
    else:
        print(-1)

 

 

2. 정답 코드

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

 

m = 5, n = 7이라고 했을 때

0 - 35까지의 테이블을 만들어보면

x = 0 ~ m -1 까지

y = 0 ~ n -1 까지 반복된다.

 

m, n, x, y 모든 값에서 1을 빼 나머지 연산을 가능하게 변환시킨다.

 

i번째 카잉 달력을  i: <i%M, i%N>

으로 나타낼 수 있다. 이를 통해

x과 3이고 y가 2일 경우  m, n 중 하나를 고정해둔다.

i : <i*M+3, y> 꼴로 두고

y가 2일 경우만 찾아주면 된다.

 

O(n)으로 해결.