목록중국인의 나머지 정리 (1)

영원히 남는 기록, 재밌게 쓰자

백준 [6064] 카잉 달력 (JAVA)

문제풀이문제 그대로 구현을 한다면 시간 초과가 발생한다. 나머지 정리와 조금의 응용이 필요했다.year가 될 수 있는 최대 값은 M, N의 최소 공배수가 될 수 있다. 최소 x 부터 시작하여 M, y 부터 시작하여 N을 만족해야 한다.year % M = xyear % N = y위 두 조건을 만족하여아 하는데 다르게 말하면 year가 M의 공배수 + x 이면 된다.그래서 최소 year = x부터 M만큼 증가시키면 1번 조건을 만족하고 그 떄의 year % N == y이면 위 두 조건을 만족할 수 있다. 하지만 한가지 예외가 10 12 10 6 인 경우 즉, 마지막 해와 N이 같은 경우 답을 체크하지 못함그래서 반복문에 들어가기 전 x와 y에 -1씩 해준 뒤 나머지 정리를 수행마지막 출력 때 year + 1..
Algorithm/백준 2024. 6. 28. 11:59
이전 Prev 1 Next 다음