백준 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님(강산 님)의 네이버 블로그에 자세히 나와있으니 원하시는 분은 들어가보시는 것을 추천드립니다.

	#include <bits/stdc++.h>
	using namespace std;
	typedef pair<int, int> pii;
	// 중국인의 나머지 정리
	// ax = 1 (mod b) 인 x 구하기 , 확장 유클리드
	pii ext_gcd(int a, int b){
	if(b){
	pii tmp = ext_gcd(b,a%b);
	return pii(tmp.second, tmp.first - (a/b)*tmp.second);
	}
	else return pii(1,0);
	}
	int mod_inv(int a, int tt){
	return (ext_gcd(a,tt).first + tt)%tt;
	}
	// ~15, ~28, ~19
	int E, S, M;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> E >> S >> M;
	int N = 15*28*19;
	int N_1 = N/15;
	int N_2 = N/28;
	int N_3 = N/19;
	// ( M_1 * N-1 ) + ( m_1 * 15 ) = 1
	// 즉 M_1 * N_1 = 1 ( mod 15 ) 를 구해야 한다.
	int M_1 = mod_inv(N_1,15);
	int M_2 = mod_inv(N_2,28);
	int M_3 = mod_inv(N_3,19);
	long long ans = E*N_1*M_1 + S*N_2*M_2 + M*N_3*M_3;
	ans%=N;
	while(ans<=0) ans+=N;
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 1476.cpp hosted with ❤ by GitHub