19. 프로젝트 오일러 #19 : 20세기의 매달 1일이 일요일인 수 계산하기

이 문제는 윤년을 올바르게 찾을 수 있는가를 찾아내는 문제라고 생각합니다.

C/C++ 에서는 time.h 헤더 파일에 있는 mktime() 함수를 이용하면 손쉽게 풀 수 있는 문제이기도 하죠.  그러나 저는 조금 다르게 찾아볼려고 노력을 했습니다.  (mktime() 함수를 이용하면 윤초 계산도 들어가는지, y년 m월 1일 0시 0분 0초의 요일이 다르게 나오네요.  1시로 옮기니 정확하게 나옵니다.)

사람들에게 1년 주기는 어떤 기준인가를 물어보면, 올바르게 아는 사람들은 적습니다.

아마 많은 분들은 지구가 태양 주위를 한바퀴 도는데 걸리는 시간이라고 생각할겁니다.

아, 아니었나요?  반문하시는 분들도 계실 것 같네요.

정확하게는 춘분점에서 다음번 춘분점까지 걸리는 시간이 1년입니다.  지구가 태양을 한바퀴 돌기 위해서는 방금전 기준보다 아주 약간 더 깁니다.

지구는 태양을 한바퀴 돌면서, 자전도 하고 공전도 하지만, 자전 이외에도 세차운동을 합니다.  지금은 지구축 위에 북극성이 있지만, 이것은 바뀔 수 있습니다.  세차운동 주기는 2만6천년정도여서 우리가 살면서 세차운동을 경험하는 것은 거의 불가능합니다.  태어난 날에 대한 별자리 역시 2천년 주기로 한칸씩 바뀝니다.  즉, 예수가 태어났을 때가 12월달이라고 한다면, 지금의 사수자리가 아니라 다른 자리였을거라는 것이죠.

고대에 1년의 길이를 계산한 것도 조금 다릅니다.  가끔씩 우리의 찬란한 문화유산 이야기할 때, 신라의 첨성대 이야기 나오면서 1년의 365일하고 1/4일이었다고 이야기하면 조금 웃습니다.

일단 첨성대에 사용된 돌의 갯수가 365개가 아닐뿐더러, 굳이 그렇다고 해도, 이미 중국 등에서 널리 알려진 역법입니다.  율리우스력은 기원전 45년(선덕여왕은 700년후)에 1년을 365일하고 1/4일이라고 규정하고 있습니다.  또한 30일과 31일을 한달로 하고, 남은 달은 2월이 됩니다.  (왜 하필이면 2월일까 하겠지만, 고대 로마 달력에서는 3월이 1월이었을것입니다.  현재까지 내려오는 달의 이름 중, 7을 뜻하는 Setember는 9월, 8을 뜻하는 October는 10월, 9를 뜻하는 November는 11월, 10을 뜻하는 December는 12월인 것을 보면 알 수 있습니다.)

태양력인 1년의 길이는 약, 365.2422일입니다.  태양력이라는 것은 춘분간의 길이를 뜻합니다.  이 경우 4년에 한번씩 윤년을 두어 1일을 더함으로써, 365.25일이 되고요.  100년에 한번씩 윤년을 없앰으로써 365.24일이 됩니다.  400년에 한번씩 윤년을 둠으로써 365.2425일이 됩니다.  그레고리력은 1582년 교황 그레고리오의 이름을 따서 만들어졌고, 현재까지도 사용하고 있는 달력입니다.  1600년동안 잘못된 날수가 12일정도가 되니, 아마도 로마시대에는 춘분이 1월1일이었지 않을까 하네요.

제가 프로그램을 작성하면서, 일단 염두에 두었던 것은 일반적인 계산식으로 기원후 1년 1월 1일부터의 날짜수를 계산할 수 있지 않을까 한 것이었습니다.  그런데, 그게 쉽지 않네요.  그래서 3월부터 31일, 30일, ..., 28일(또는 29일)이 되는 것을 식으로 만들어보았습니다.

여기서는 간단하게 프로그램으로 파라미터를 추출해보았습니다.

[GetParameters]

void GetParameters()
{
    int m[] = { 31, 30, 31, 30, 31, 31, 30, 31, 30, 31, 31 };
    for( int a = 1 ; a <= 11 ; a++ )
    {
        for( int b = 30*a-1 ; b <= 31*a+1 ; b++ )
        {
            for( int c = 0 ; c < 5 ; c++ )
            {
                int t = 0, i;
                for( i = 1 ; i < 12 ; i++ )
                {
                    int s = (b*i + c)/a;
                    if( s-t != m[i-1] ) break;
                    t = s;
                }
                if( i == 12 ) printf("(%d, %d, %d)\n", a, b, c);
            }
        }
    }
}

위 함수를 돌린 결과 저는 5, 153, 2 라는 파라미터를 얻을 수 있었습니다.  즉, 3월부터 세어나갈때, 이듬해 1월까지의 날수는 다음과 같은 공식으로 찾을 수 있습니다.

그리고 윤년을 계산하는 식은,

으로 했습니다.  C/C++에서는 정수형 연산을 실행하면 자동으로 소숫점 이하 버림을 하므로, 별 신경을 안 써도 될겁니다.

솔직히 프로그램에서는 위 공식을 이용해서 만들기보다는, 배열에 적산한 날짜수를 넣는 것이 더 빠를겁니다.  그냥 짜면 별로 재미없을까봐.. 

그래서 나온 #19의 문제 풀이용 C/C++ 소스는 다음과 같습니다.

[19.cpp]

#include <stdio.h>
#include <time.h>

int GetWeekDay(int y, int m, int d);

int main()
{
    int count = 0;

    for( int y = 1901 ; y <= 2000 ; y++ )
    {
        for( int m = 1 ; m <= 12 ; m++ )
        {
            if( GetWeekDay(y, m, 1) == 0 ) count++;
        }
    }
    printf("Ans = %d\n", count);
}

int GetWeekDay(int y, int m, int d)
{
    if( m <= 2 ) { m += 9; y += 4799; } else { m -= 3; y += 4800; }
    int days = 365*y + y/4 - y/100 + y/400 + (153*m+2)/5 + d - 32045;
    return (days+1)%7;
}