문제 개요
임의의 연도 Y가 주어졌을 때, Y와 완전히 똑같은 달력을 가지는 다음 연도를 찾는 것이 이 글의 목표입니다. 실제로 2017년의 달력은 2023년의 달력과 동일합니다.
동일한 달력 연도의 조건
어떤 연도 X가 이전 연도 Y와 동일한 달력을 가지려면 다음 두 가지 조건을 모두 만족해야 합니다.
- 연도 X가 Y와 같은 요일로 시작해야 합니다.
- Y가 윤년이면 X도 윤년이어야 하고, Y가 평년이면 X도 평년이어야 합니다.
알고리즘 아이디어
접근 방법은 단순합니다. 기준 연도의 바로 다음 해부터 연도를 하나씩 순서대로 검사하면서, 요일이 며칠씩 앞으로 이동했는지 누적 일수를 계속 추적합니다. 이동한 총 일수가 7일이 되면, 그 해는 기준 연도와 같은 요일에 시작한다는 의미입니다.
동시에 현재 연도가 윤년인지 여부도 확인합니다. 윤년이라면 기준 연도 Y 역시 윤년인지 함께 비교해야 하며, 두 조건이 모두 충족되는 순간 해당 연도를 반환하면 됩니다.
요일 이동량 계산의 핵심 원리는 다음과 같습니다. 평년은 365일, 윤년은 366일입니다. 365를 7로 나눈 나머지는 1이고, 366을 7로 나눈 나머지는 2이므로, 평년은 시작 요일을 1칸, 윤년은 2칸 앞으로 믿게 됩니다. 따라서 아래 코드의 countExtraDays 함수는 윤년이면 2, 평년이면 1을 반환하고, 누적값을 7로 나눈 나머지가 0이 되는 지점에서 같은 요일의 해를 찾아냅니다.
예제 코드
#include<iostream>
using namespace std;
int countExtraDays(int y) {
if (y%400==0 || y%100!=0 && y%4==0)
return 2;
return 1;
}
int nextIdenticalYear(int y) {
int days = countExtraDays(y);
int x = y + 1;
for (int sum=0; ; x++) {
sum = (sum + countExtraDays(x)) % 7;
if ( sum==0 && (countExtraDays(x) == days))
return x;
}
return x;
}
int main() {
int curr = 2019;
cout << "Next identical year of " << curr <<" is: " << nextIdenticalYear(curr);
}
실행 결과
Next identical year of 2019 is: 2030
위 코드를 실행하면 2019년과 동일한 달력을 가지는 다음 연도로 2030년이 출력됩니다. 2020년부터 2029년까지의 요일 이동량을 누적하다 보니, 시작 요일과 윤년 여부가 모두 일치하는 첫 번째 해가 2030년인 것입니다.