[Project Euler] Problem 019

 

public class Problem019 {
    
    public static void main(String[] args) {
        System.out.println(run());
    }
    
    public static String run() {
        int sunday;
        int count = 0;
        int today = 1;
        
        for(int month = 1; month <= 12; month++) {
            switch(month) {
                case 1: case 3:  case 5: case 7: case 8: case 10: case 12:
                    today += 31;
                    break;
                case 2:
                    today += 28;
                    break;    
                case 4: case 6: case 9: case 11:
                    today += 30;
                    break;
                    
            }
        }
        
        sunday = 1 + (7 - (today % 7));
        
        for(int year = 1901; year <= 2000; year++) {
            for(int month = 1; month <= 12; month++) {                
                if(sunday == 1) { count++; }
                
                switch(month) {
                    case 1: case 3: case 5: case 7: case 8: case 10: case 12:
                        while(sunday <= 31) { 
                            sunday += 7;
                        }
                        
                        sunday -= 31;
                        break;
                    case 2:
                        if(((year%4 == 0) && (year%100 != 0)) || (year%400 == 0)) {
                            while(sunday < 29) {
                                sunday += 7;
                            }
                            
                            sunday -= 29;
                        } else {
                            while(sunday < 28) {
                                sunday += 7;
                            }
                            
                            sunday -= 28;
                        }
                        break;
                    case 4: case 6: case 9: case 11:                    
                        while(sunday <= 30) {
                            sunday += 7;
                        }
                        
                        sunday -= 30;
                        break;
                }
            }
        }
        
        return Integer.toString(count);
    }
}

 

 

 

정답: 171

실행 시간: 0.0004초

 

첫 번째 반복문에서는 1900년 1월 1일이 월요일인 것을 토대로 1901년 1월 1일이 무슨 요일인지 알아낸 다음, 다시 이를 토대로 첫 일요일은 며칠인지 알아낸다. 1900년 1월 1일이 월요일이므로  today 를 7로 나눈 나머지가 1이면 월요일, 2면 화요일, …, 0이면 일요일이다.

따라서 실제 1901년 1월의 첫 일요일은 1월  1 + 7 - today%7 일이다. 

이제 이 날짜를  sunday 에 저장하고 각 달에 맞게 날짜를 조정한다.

예를 들어 1월 6일부터 7씩 더하면 13일, 20일, 27일, 34일이 된다. 34에서 31을 뺀 3이 1월 27일의 다음 일요일의 날짜가 된다. 실제로 1901년 2월 3일은 일요일이다.

 

switch 문이 아닌 배열로 풀면 다음과 같다(C).

 

#include <stdio.h>
 
int main()
{
    int day = 1; 
    int year, month;
    int count = 0;
    int isLeap;
 
    int arr[2][12] = { 
        { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 },
        { 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }
    };
 
    for (month = 1; month <= 12; ++month) 
    {
        day += arr[0][month - 1];
    }
    day = 1 + (7 - (day % 7));
 
    for (year = 1901; year <= 2000; ++year) 
    {
        isLeap = ((year % 4 == 0) && (year % 100 != 0)) || (year % 400 == 0);
 
        for (month = 1; month <= 12; ++month)
        {
            count += (day == 1);
 
            while (day <= arr[isLeap][month - 1])
            {
                day += 7;
            }
 
            day -= arr[isLeap][month - 1];
        }
    }
 
    printf("%d\n", count);
 
    return 0;
}
 

윤년 때문에 풀이가 복잡해진다.

 isLeap 는 윤년일 때는 1이고 아니면 0이므로 2차원 배열에서 인덱스로 사용할 수 있다.