백준 6064번 카잉

사실 이문제는 딱히 적을생각이 없었는데 중국인의 나머지 정리가 도저히 이해되지 않아 적어본다

 

우선 처음에 썼던 방법은 브루트 포스를 이용해서 풀었는데 당연히 n이 최대 40000이므로 n^2으로 풀면 시간초과다

 

다음으로 도저히 방법을 모르겠어서 x,y한쪽을 고정하고 값을 더해서 풀어보자고 생각을 했는데

반복문 탈출조건이 없어서 답이 나오질 않았다

 

그래서 도저히 모르겠어 찾아본 결과 중국인의 나머지정리를 사용해야한다고 한다

 

사실 정확한 이론은 이해하고 있지 않아도 코드 작성은 가능하다

 

import sys

n=int(sys.stdin.readline().rstrip())
for _ in range(n):
    m,n,x,y=map(int,sys.stdin.readline().rstrip().split())

    year=x

    while (year%n!=y) and year<=m*n:
        year+=m

    if year%n==y:
        print(year)
    else:
        print(-1)

이렇게 작성했다 그런데 문제가 되는 부분은 저 m*n부분이다. 저기가 LCM(최소공배수)가 되게 하면 조금더 최적화 되겠지만 일단은 저렇게 작성했다.

그런데 왜 저기가 최소공배수가 되는지를 이해하지 못했다

 

예를들어 m=10,n=12일때 종말수는 60이다. m과n의 최소공배수가 종말수가 되는거다.

이론은 파악을 했는데 왜 이렇게 되는지를 모르겠다.

 

주기가 반복되기때문이라고 하는데 뭔가 이해는 했는데 설명하라하면 쉽지는 않다.

 

아무튼 저 코드로 제출을 하면

 

왜요?

 

다시 잘 생각해보니 y가 n일때가 문제가 된다

이런식으로 말이다

10이 나와야하는데 -1이 나온다

import sys

n=int(sys.stdin.readline().rstrip())
for _ in range(n):
    m,n,x,y=map(int,sys.stdin.readline().rstrip().split())
    year=x
    if y==n:
        y=0
    while (year%n!=y) and year<=m*n:
        year+=m

    if year%n==y:
        print(year)
    else:
        print(-1)

이렇게 수정해줬다 많이 헷갈린다

반복문은 최대 n번 도니까 시간초과 걱정도 없다.

다만 아까 말한것처럼 lcm으로 해주면 더 최적화 가능하다 또 m과 n중에서 더큰걸 골라서 반복문은 더 작은 쪽으로 돌게 해주는 식도 가능하다.

느려...

 

오늘도 겸손함 잔뜩 주입당했다...