[PS] BOJ6064 카잉달력 ( math, bruteforce ) With 파이썬

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

6064번: 카잉 달력

 

◎ 문제풀이 

 

단순히 +1 씩 증가시켜 탐색하면 시간초과 나오는 문제이다. <x,y>는 x에 M개, y에 N개가 들어갈 수 있으므로 총 M*N개의 경우의 수를 갖는다. M과 N은 최대 40,000이므로 M*N은 1,600,000,000이다. 시간제한 1초는 2억-3억 연산을 수행할 수 있는데 최대연산횟수가 16억이므로 아득히 넘어간다. 

 

위 문제는 수학으로 접근해야 풀린다. M,N이 주어졌을 때, <x,y>가 몇 번째에서 등장하는지를 구하는 문제이다.  M이 10이고 x를 3이라고 가정해보자.

 

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

 

첫번째 3은 3번째이고 ( i = 0 )

두번째 3은 13번째이다. ( i = 1 )

세번째 3은 23번째이다. ( i = 2 )

.

.

k번째 3은 3+10*i 번째이다. 즉, k = 3 + 10 * i 이다.  일반화하면 k = x + M*i 이다. y도 동일하다. k = y + N*j 이다. 

 

여기서 j는 자연수이다. 

 k = y + N*j 

 j =( k- y ) / N 

 

k-y가 N으로 나누어 자연수가 나오려면 N으로 나누어 떨어져야 한다. 즉, 나머지가 0이어야 한다.

 

k는 x+Mi이다. 고로, x에 M을 i번 반복하여 더한 값(k)에 y를 빼고 N으로 나눈값이 0이 될 때의 k가 정답이다. 이를 코드로 표현해 보자.

 

◎ 코드

t = int(input())

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

 

x에 += M을 반복하여 더하면 k가 된다. 그러므로 x가 곧 k이다.  x-y 값이 N으로 나누어 떨어질 때의 x를 return하면 된다. 

 

while문의 조건범위를 M*N으로 하였다. <x,y>의 경우의 수가 M*N이므로 최대 M*N번째 경우의 수까지 나올 수 있다.  M*N은 최대 1,600,000,000 으로 x가 +1씩 증가하면 시간초과가 나왔다. 위 코드는 x가 +M씩 증가하므로 시간복잡도는 O(M*N)이 아니라 O(N)이 된다. 이는 최대 연산횟수가 40,000으로 시간제한 1초 내에 처리가 가능하다.