You are given the following information, but you may prefer to do some research for yourself.
- 1 Jan 1900 was a Monday.
- Thirty days has September,
April, June and November.
All the rest have thirty-one,
Saving February alone,
Which has twenty-eight, rain or shine.
And on leap years, twenty-nine. - A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.
How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?
[출처 - projecteuler.net/]
점점 흥미로운 문제가 많아지는 것 같습니다. 이번문제는 20세기에 해당하는 기간중에 매달 1일이 일요일인 경우가 몇번이나 존재하는지 계산하는 문제입니다. 해당문제에서는 1900년 1월 1일을 기준으로 설명을 하는데... 보통 프로그래밍 언어에서 now, date등 함수를 사용해서 로직을 구성하면 그 처음은 항상 1900년 1월 1일을 기준으로 현재까지의 지나온 날을 계산해서 리턴해 줍니다.
그 이유는, 컴퓨터의 등장 시점과 맞물려 해당일이 그 기준으로 맞춰진 것이 아닐까 생각이 됩니다. Microsoft의 Excel에서도 날짜를 사용하면 항상 1900-1-1이 기준이고 그 값은 1이 됩니다.
날짜를 계산하기 위해서는 1년을 구성하는 12달이 가지고 있는 일수에 대한 구성을 생각해 봐야합니다. 보통 1년은 365일 이라고 알고 있지만, 오랜시간이 지나면서 조금씩 날짜가 차이가 나는 현상이 있었고... 그를 보정하기 위해서 leap year... 즉 윤년이 생겨났습니다.
윤년은 1년이 365일이 아닌 366로 구성된 년도이며, 그 판단기준은 아래와 같습니다.
- 윤년은 1900년 1월 1일을 기준으로 매 4년마다 1번씩 돌아온다.
- 하지만, 100년마다는 윤년으로 산정하지 않는다.
- 그럼에도 불구하고, 400년 마다는 윤년으로 산정을 한다.
그러 다음으로, 윤년과 평년의 월 구성은 아래와 같습니다.
- 평년 - 31일, 2월: 28일, 31일, 30일, 31일, 30일, 31일, 31일, 30일, 31일, 30일, 31일
- 윤년 - 31일, 2월: 29일, 31일, 30일, 31일, 30일, 31일, 31일, 30일, 31일, 30일, 31일
이렇게 2월에 대한 일수만 1일 차이가 납니다. 이제 문제 해결을 위한 준비는 마쳤습니다. 그럼 실제 문제에 들어가 보겠습니다.
1. Basic
이 문제를 해결하기 위해서, 저는 아래와 같이 해결해 보았습니다.
- Leap Year를 판단하는 매서드를 우선 제작한다.
- 구하고자 하는 기간의 시작 년/월에 대해서, 1900년 1월부터 해당 월까지의 날짜를 계산하여 시작 년/월의 1일에 해당하는 요일을 구한다.
- 시작 년/월 부터 ~ 종료 년/월 까지 월별로 1일이 일요일인지 여부를 확인하여 결과에 반영한다.
그럼 하나하나 차근차근 보겠습니다.
[1. 윤년판단 메서드]
def CntLeafYear(no):
res = no // 4
res -= no // 100
res += no // 400
return res
def ChkLeafYear(no):
normalYear = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
leafYear = [0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
if no % 4 == 0:
if no % 400 == 0:
monthOfDay = leafYear
elif no % 100 == 0:
monthOfDay = normalYear
else:
monthOfDay = leafYear
else:
monthOfDay = normalYear
return monthOfDay총 2가지 입니다. CntLeafYear는 1900년을 기준으로 구하고자 하는 시작 년까지의 윤년의 개수를 구해서 리턴합니다. 그리고 두번째는 ChkLeafYear에서 평년과 윤년의 경우에 대해서 각 월별로 일의 개수에 해당하는 list를 판단해서 리턴합니다.
[2. 시작 년월의 요일판단]
startDate = [1901, 1 , 1]
endDate = [2000, 12 , 31]
# 1900/1/1 기준으로 주어진 시작년도의 1/1 까지의 날짜수 세기
defYearCnt = CntLeafYear(1899) * 366 + (1899 - CntLeafYear(1899)) * 365
startYearCnt = CntLeafYear(startDate[0] - 1) * 366 + (startDate[0] - 1 - CntLeafYear(startDate[0] - 1)) * 365
startPoint = startYearCnt - defYearCnt + 1
# 주어진 시작년도의 1/1 의 요일 구하기
print('1900/1/1 기준 날짜 수 : ', startPoint)
print('요일 : ', startPoint % 7)
# 시작년도의 월까지 계산
monthOfDay = ChkLeafYear(startDate[0])
for i in range(1, startDate[1]):
startPoint += monthOfDay[i]
# 주어진 시작년도/월의 1일에 해당하는 요일 구하기
print('시작년도/월 기준 날짜 수 : ', startPoint)
print('요일 : ', startPoint % 7)문제의 조건과 같이 시작 년/월/일, 종료 년/월/일을 세팅합니다. 그리고, 위에서 제작한 메서드를 통해서 1900년 1월 1일 부터 시작 년/월의 1일까지에 해당하는 일 수를 계산합니다.
이때, 우선 년도의 1월 1일까지를 구하고... 그 다음에 시작 월까지의 각 월별 일수를 더해 줍니다. 그렇게 되면 startPoint 에 그 결과가 저장됩니다. 이 기준은 항상 원하는 년/월의 1일에 해당하는 값입니다.
위의 로직을 돌리면... 1901년 1월 1일의 요일을 출력하게 되는데... 0 ~ 6까지가 각 각 일요일 ~ 토요일로 구성이 됩니다.
[결과]
1900/1/1 기준 날짜 수 : 366
요일 : 2
시작년도/월 기준 날짜 수 : 366
요일 : 2그 결과는 2로 "화요일" 입니다. 달력을 통해서 확인하면 일치함을 알 수 있습니다.
[3. 시작 년/월 부터 ~ 종료 년/월 계산]
이제는 시작 년/월 부터... 종료 년/월까지 계속 loop를 돌면서 해당하는 월의 일수를 더해주고, 그 결과를 7로 나누어서 결과가 0이면 결과에 계속 +1을 해주면 됩니다. 그렇다면 전체 코드는 아래와 같습니다.
import time
def CntLeafYear(no):
res = no // 4
res -= no // 100
res += no // 400
return res
def ChkLeafYear(no):
normalYear = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
leafYear = [0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
if no % 4 == 0:
if no % 400 == 0:
monthOfDay = leafYear
elif no % 100 == 0:
monthOfDay = normalYear
else:
monthOfDay = leafYear
else:
monthOfDay = normalYear
return monthOfDay
if __name__ == '__main__':
tc = int(input())
for t in range(tc):
startDate = [1901, 1 , 1]
endDate = [2000, 12 , 31]
# 1900/1/1 기준으로 주어진 시작년도의 1/1 까지의 날짜수 세기
defYearCnt = CntLeafYear(1899) * 366 + (1899 - CntLeafYear(1899)) * 365
startYearCnt = CntLeafYear(startDate[0] - 1) * 366 + (startDate[0] - 1 - CntLeafYear(startDate[0] - 1)) * 365
startPoint = startYearCnt - defYearCnt + 1
# 주어진 시작년도의 1/1 의 요일 구하기
print('1900/1/1 기준 날짜 수 : ', startPoint)
print('요일 : ', startPoint % 7)
# 시작년도의 월까지 계산
monthOfDay = ChkLeafYear(startDate[0])
for i in range(1, startDate[1]):
startPoint += monthOfDay[i]
# 주어진 시작년도/월의 1일에 해당하는 요일 구하기
print('시작년도/월 기준 날짜 수 : ', startPoint)
print('요일 : ', startPoint % 7)
# Main 로직구현
### 시작 값의 일에 해당하는 값이 1일 경우, 로직 추가
res = 0
if startPoint % 7 == 0 and startDate[2] == 1:
res += 1
### 목표의 년도/ 월까지
nowYear = startDate[0]
nowMonth = startDate[1]
endYear = endDate[0]
endMonth = endDate[1]
while endYear >= nowYear:
monthOfDay = ChkLeafYear(nowYear)
print(nowYear, monthOfDay)
if nowYear == startDate[0]:
for i in range(nowMonth, 13):
startPoint += monthOfDay[i]
if startPoint % 7 == 0:
res += 1
elif endYear == nowYear:
for i in range(1, endMonth):
startPoint += monthOfDay[i]
if startPoint % 7 == 0:
res += 1
elif endYear > nowYear:
for i in range(1, 13):
startPoint += monthOfDay[i]
if startPoint % 7 == 0:
res += 1
nowYear += 1
print("결과 : ", res)[결과]
1996 [0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
1997 [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
1998 [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
1999 [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
2000 [0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
결과 : 171한번 각 년도별로, 평년인지 윤년인지 잘 판단하여 list를 가져오는지 확인을 해 보았습니다. 최종 결과는 일치함으로 성공했습니다.
- Ayotera Lab -
댓글