오일러 프로젝트 19
다음은 달력에 관한 몇 가지 일반적인 정보입니다 (필요한 경우 좀 더 연구를 해 보셔도 좋습니다).
- 1900년 1월 1일은 월요일이다.
- 4월, 6월, 9월, 11월은 30일까지 있고, 1월, 3월, 5월, 7월, 8월, 10월, 12월은 * 31일까지 있다.
- 2월은 28일이지만, 윤년에는 29일까지 있다.
- 윤년은 연도를 4로 나누어 떨어지는 해를 말한다. 하지만 400으로 나누어 떨어지지 않는 매 100년째는 윤년이 아니며, 400으로 나누어 떨어지면 윤년이다
20세기 (1901년 1월 1일 ~ 2000년 12월 31일) 에서, 매월 1일이 일요일인 경우는 총 몇 번입니까?
접근
날짜를 구성하는 정보는 연도, 월, 일이 있고, 각 월은 그 크기가 미리 정해져 있다. 따라서 일자 값을 하루씩 증가시켜 나가면서 매월 1일이 될 때 그날의 요일값을 검사해보면 된다.
요일은 편의상 일요일을 0, 토요일을 6으로 두면 하루가 지날 때마다 1을 더한 후 7로 나눈 나머지를 구하면 7일 주기로 순환하는 값을 만들 수 있다.
## !! 이 코드는 뭔가 빠졌기 때문에 틀린 답을 계산합니다
y, m, d, w = 1900, 1, 1, 1
result = 0
# days는 각 월의 일수를 나타낸다.
days = (31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)
while y < 2001:
d, w = d + 1, (w + 1) % 7
if d > days[m - 1]:
m, d = m + 1, 1
if m > 12:
y, m = y + 1, 1
# 검사
if 1900 < y < 2001 and d == 1 and w == 0:
result += 1
print(result)
그런데 문제가 하나 있다. 위 코드는 모든 해의 2월이 28일까지만 있다고 가정한다. 윤년인 해의 2월은 29일까지가 있기 때문에 이를 고려해야 한다. 그러면 월이 바뀌는 시점의 로직이 “이번달이 2월이고 올해가 윤년이면 하루를 더한 날짜와 비교”해야 하는데 이게 좀 번거롭기 때문에, days를 days1 과 days2 로 구분해서 만들어두고, 윤년인 해에만 days2에서 매달의 날짜수를 비교하게하는 것이 코드가 간단할 것이다.
참고로 윤년을 계산하는 로직은 다음과 같다.
# 계산로직
def is_leap(year: int) -> bool:
if year % 4 == 0:
if year % 100 == 0:
if year % 400 == 0:
return True
return False
reutrn True
return False이렇게 하는 것은 보통 4년마다 한 번 이라는 기준부터 적용하기 때문인데, 기준을 큰 단위부터 놓고 생각하면
- 400으로 나눠지면 윤년이다.
- 100으로 나눠지면 윤년이 아니다.
- 4로 나눠지면 윤년이다.
로직이 더 간단해 질 수 있다. 왜냐면 100, 4는 모두 400의 약수이기 때문이다.
is_leap = lambda year: year % 400 == 0 or year % 100 > 0 and year % 4 == 0윤년을 고려하여 개선한 코드는 다음과 같다.
y, m, d, w = 1900, 1, 1, 1
result = 0
is_leap = lambda year: year % 400 == 0 or year % 100 > 0 and year % 4 == 0
# days는 각 월의 일수를 나타낸다.
days1 = (31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)
days2 = (31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)
while y < 2001:
d, w = d + 1, (w + 1) % 7
if d > (days2[m - 1] if is_leap(y) else days1[m-1]):
m, d = m + 1, 1
if m > 12:
y, m = y + 1, 1
# 검사
if 1900 < y < 2001 and d == 1 and w == 0:
result += 1
print(result)사실 우리의 관심사는 매달 1일일 뿐이므로, 매 달의 날짜를 더하는 방식으로 계산할 수도 있다. 1월 1일에서 2월 1일로 넘어갈 때 m에는 1을 더하고, w 에는 (w + 31) % 7 하면 되는 것이다.
y, m, w = 1900, 1, 1, 1
result = 0
is_leap = lambda year: year % 400 == 0 or year % 100 > 0 and year % 4 == 0
# days는 각 월의 일수를 나타낸다.
days1 = (31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)
days2 = (31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)
while y < 2001:
m, w = m + 1, (w + (days2[m - 1] if is_leap(y) else days1[m-1])) % 7
# 검사
if m > 12:
y, m = y + 1, 1
if 1900 < y < 2001 and d == 1 and w == 0:
result += 1
print(result)datetime 모듈을 사용한 풀이
datetime.datetime을 사용하면 달력 상의 날짜를 이용한 계산을 손쉽게 할 수 있다. 특히 .weekday()를 사용하면 요일을 바로 알아낼 수 있다. 단 주의할 점은 (이유는 모르겠지만) .weekday() 메소드는 월요일을 0, 일요일을 6으로 하는 주기를 가지고 있다. (요일을 정수로 표현하는 방식은 프로그래밍 언어마다도 다 다르다.)
특정한 시점에 하루를 더하여 다음날의 날짜를 만들 때에는 datetime.timedelta 를 정의하여 이 값을 datetime.datetime에 더해주면 된다. weekday() 는 달력을 기준으로 날짜를 계산하므로 문제에서 제시한 시작 시점인 1900년 1월 1일부터 시작할 필요가 없다. (단, timedelta는 최대 단위가 weeks 기준이라서 월별로 점프할 수는 없고 하루씩 날짜를 더해야 한다.)
%%time
from datetime import datetime, timedelta
t, d = datetime(1901, 1, 1), timedelta(days=1)
result = 0
while t.year < 2001:
if t.day == 1 and t.weekday() == 6:
result += 1
t += d
print(result)
