백준 1476번 날짜 계산

< 백준 1476번 날짜 계산 - 마포 코딩박 >

사용한 알고리즘: 수학 ( 확장 유클리드, 중국인의 나머지 정리 )


 주기가 15, 28, 19 인 E, S, M의 값을 각각 주고, 몇년이 흘렀는지 계산하는 문제였습니다.
 사실 중국인의 나머지 정리와 확장 유클리드에 대한 지식이 없다면 해결하기 힘든 문제였던 것 같습니다.

문제풀이는 다음과 같습니다.

(1) (수학)
 중국인의 나머지 정리 개념은 스킵하고 이를 통한 풀이만 쓰겠습니다.
 15, 28, 19 는 서로 서로소입니다. 입력 E , S, M 이 주어지고, N = 15*28*19, N1=N/15, N2=N/28, N3=N/19 라 합시다.
 M1*N1=1 (mod 15) , M2*N2=1 (mod 28) , M3*N3=1 (mod 19) 인 M1,M2,M3 를 구하면 구하고자 하는 답 ans = (E*N1*M1+S*N2*M2+M*M3*N3)%N 입니다.
 (이때 ans=0 인 경우 0년 후는 답이 아니니 ans = N 입니다.)

확장 유클리드와 중국인의 마지막 정리에 대해서는 ries님(강산 님)의 네이버 블로그에 자세히 나와있으니 원하시는 분은 들어가보시는 것을 추천드립니다.