문제 (English)
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)?
Answer: 171
문제 분석
두 날자 사이에서 매달 초가 일요일이 되는 달이 몇 개인지 세는 문제이다.
이러한 계산을 위해서는,
- 그레고리역(현재 우리가 쓰는 양력이다.)의 윤년 규칙을 알아야 한다.
- 요일이란 것이 법7(modulation 7)을 기반으로 하는 거여서, 법 7을 기반으로 한 계산에 익숙해야 한다.
풀이 1
1900.1.1일이 월요일이라고 했으니, 다음과 같이 풀이 방법을 생각해 보자.
- 1900.1.1일부터 시작해서 한 달씩 건너 띄면서 날자를 세어본다.
- 즉, 1900.1.1일 다음은 같은 해의 2.1일. 1월이 31일이므로 1+31일 지난 것
- 그다음은 3.1일은, 윤년이 아니라면 2월달 28일 더해서 60일, 만약 윤년이라면 29일을 더한다. (1900년은 윤년이 아니기에 28을 더하면 되겠다.)
- 이렇게 더한 값을 %7 해준다. 60%7=4 --> 1:월, 2:화, 3:수, 4:목, 5:금, 6:토, 0:일
- 이렇게 더해 나가는데, 만약 주어진 기간이 1902년 2월 1일부터라면, 그 이전인 1902.1.1일까지는 날수만을 세고 그날의 요일은 계산하지 않는다.
- 주어진 기간 이후부터는(예를 들어 1902.2.1일부터), 매달 초일이 일요일인지를 계산해 보고, 카운트를 한다.
여기서 해당 연도가 윤년인지는 다음과 같은 규칙. 윤년에는 2월이 29일이다.
- year가 4의 배수이면 윤년
- 그러나, year가 100의 배수이면 윤년이 아니다.
- 또 그러나, year가 400의 배수이면 윤년이다.
이를 함수로 구현하면 다음과 같다.
fn is_leap(y:usize) -> bool {
if y % 400 == 0 {return true;}
if y % 100 == 0 {return false;}
if y % 4 == 0 {return true;}
return false;
}
윤년인지는, 간단하게 한 줄로 표현할 수도 있다.
if (y%400==0 || (y%4==0 && y%100!=0))
아래는 위와 같은 논리로 두 Date 사이에서, 매달 1월 1일이 일요일인 개수를 세는 함수이다.
#[cfg(test)]
fn answer((y1,m1,d1):(usize,usize,usize), (y2,m2,_d2):(usize,usize,usize)) -> usize{
let month = [0,31,28,31,30,31,30,31,31,30,31,30,31];
let mut ans:usize = 0;
let mut diff:usize = 1;
'outer: for y in 1900..=y2{
for m in 1..=12 {
if y == y2 && m >= m2 { break 'outer;}
diff += if is_leap(y) && m==2 {month[m]+1} else {month[m]};
if y < y1 || (y==y1 && m < m1) || (y==y1 && m==m1 && d1 > 1) {continue;}
if diff % 7 == 0 {ans += 1;}
}
}
return ans;
}
#[cfg(test)]
fn is_leap(y:usize) -> bool {
if y % 400 == 0 {return true;}
if y % 100 == 0 {return false;}
if y % 4 == 0 {return true;}
return false;
}
위 코드는 1900년과 가까운 기간의 연도에 대해서는 빠른 시간에 동작한다.
그러나, 만약 서기 100만 년 1월1일부터 100만년 1월 31일까지를 계산하라고하면, 1900년부터 100만년 1월 1일이 될 때까지 날수를 더해나가야 해서 비효율적이다.
실제로 hackerrank 사이트에서는 연도가 $10^{16}$까지를 input으로 하기에, 위 코드로는 통과하지 못한다.
좀 다른 방법이 필요하겠다.
풀이 2
1900.1.1일을 기준으로 해서 날수를 세가면서 요일을 계산하는 것이 아니라, 그냥 어떤 Date가 주어지면 해당 일의 요일이 어떻게 되는지를 수식으로 계산하는 함수를 만들어보자.
그러고 나서, 입력으로 주어지는 두 기간 사이의 매달 1월 1일이 일요인지를 체크하면서 카운트하면 되겠다.
어떤 Date가 주어졌을 때, 그날의 요일을 계산하는 식으로는 첼러의 공식(Zeller's Congruence)이 있다.
이 공식은 수학적으로는 멋지게 보이나, 직관적이지 않고 프로그래머틱하지 않다.
새롭게 만들어보자.
기본 아이디어는 다음과 같다.
- 서기 1년 1월 1일은 월요일이다. 월요일을 1로 하자. 화요일은 2, ..., 토요일은 6, 일요일은 0
- 2024.8.12일의 요일을 구한다고 생각해 보면,
- 먼저, 2024.1.1일의 요일을 구한다. 매년 365일 혹은 366일이니, 윤년만 고려하면 쉽게 2024.1.1일까지의 날수를 구할 수 있고, 이것을 모듈레이션 7을 하면, 요일을 구할 수 있겠다.
- 그다음은 2024.1.1일부터 2024.8.1일까지의 날수를 구하고, 그로부터 요일을 구하고,
- 마지막으로 2024.8.1일부터 2024.8.12일까지의 날수를 구하고, 그로부터 요일을 구한다.
위 아이디어를 그림으로 표현하면 아래와 같다.
(1) 연도 간 요일 구하기
일반적으로 365일이고, 365%7=1이기에, 서기 1년 1월 1일에서 y 년 1월 1일의 요일은 $y % 7$이다.
예를 들어 서기 3년 1월 1일의 요일을 생각해 보면, 3년 1월 1일까지의 날 수는 2 * 365
따라서 구하는 요일은 (2 * 365 + 1) % 7 = 731 % 7 = 3 = 수요일
위 계산식 (2 * 365 + 1) % 7을 보면,
- 앞부분 2는 (y - 1)을 한 값이다. 서기 1년에서 서기 3년까지니깐 (3-1)이 된 것이다. yy=y-1로 놓자.
- 365 % 7 = 1이기에 (2 * 365 + 1) % 7 = (2 * 1 + 1) % 7 이다.
여기서 2는 (y-1)이기에, 다시 쓰면, ( yy * 1 + 1) % 7 = (yy+1) % 7
이처럼 윤년이 아닌 경우는 y % 7만을 하면, 해당 연도 y의 1월 1일 요일이 된다.
그러나, 윤년의 경우는 1년이 366일이어서 1을 더 더해줘야 한다.
윤년은, 4년, 8년, 12년처럼 4의 배수의 해에 해당하니, 계산하는 연도 사이에 4의 배수 연도가 있으면 +1을 해준다.
근데, 100의 배수의 해는 윤년이 아니니 -1을 해준다. 그리고 400의 배수가 되는 해는 다시 윤년이니 +1을 해준다.
let yy = y - 1; //if y=4 --> have to consider only for 1~3
ans = (yy + (yy/4) - (yy/100) + (yy/400) + 1) % 7;
(2) 월에 대한 요일 구하기
어떤 해의 1/1일이 요일 w일 때 m월 1일까지의 요일차이는, 1/1일부터 m/1일까지의 일수를 diff라고 하면 (w + diff) % 7이다.
예를 들어, 어떤 해의 1/1일이 1(월요일)이라고 하면, 2/1일은 1월에 있는 31일이 지난 것이기에 1+31%7=4(목요일)이 된다.
diff는 배열로 만들어서 사용하면 편하겠다.
윤년의 경우는, 2월이 28이 아니고 29일이기에, 윤년일 때 3월부터 12월까지는 (w + diff + 1) % 7로 계산해야 한다.
//2. month: yyyy/mm/1, if 2024/7/1 -> 1
let month = [0,0,31,59,90,120,151,181,212,243,273,304,334]; //x,x,Jan,Feb,Mar,...,Nov,0
ans = (ans + month[m]) % 7;
if (y%400==0 || (y%4==0 && y%100!=0)) && m > 2 {ans += 1;}
(3)일 수에 의한 요일 계산
어떤 달의 1일의 요일이 w라고 하면, 해당 월의 d일의 요일은 (w + d - 1) % 7이다.
예를 들어 2024년 7월 1일이 1(월요일)이라고 하면, 7/15일은 (1 + 15 - 1) % 7 = 1(월요일)이다.
//3. day: yyyy/mm/dd, if 2024/7/15 -> 1
ans = (ans + d - 1) % 7;
이렇게 구현한 코드는 아래와 같고, 이렇게 하면 hackerrank 사이트 문제도 통과한다.
#[cfg(test)]
fn answer1((y1,m1,d1):(usize,usize,usize), (y2,m2,_d2):(usize,usize,usize)) -> usize{
let mut ans:usize = 0;
'outer: for y in y1..=y2{
for m in 1..=12 {
if y==y1 && (m<m1 || (m==m1 && d1>1)) {continue;}
if y==y2 && m>m2 {break 'outer;}
if cal_weekaday1(y,m,1)==0 {ans += 1;}
}
}
return ans;
}
#[cfg(test)]
// Monday: 1, ... Sat: 6, Sunday: 0
fn cal_weekaday1(y:usize, m:usize, d:usize) -> usize {
let mut ans:usize;
//1. year: yyyy/1/1, if 2024/1/1 -> 1
// 365 % 7 = 1, so y*365 = y
let yy = y - 1; //if y=4 --> have to consider only for 1~3
ans = (yy + (yy/4) - (yy/100) + (yy/400) + 1) % 7;
//2. month: yyyy/mm/1, if 2024/7/1 -> 1
let month = [0,0,31,59,90,120,151,181,212,243,273,304,334]; //x,x,Jan,Feb,Mar,...,Nov,0
ans = (ans + month[m]) % 7;
if (y%400==0 || (y%4==0 && y%100!=0)) && m > 2 {ans += 1;}
//3. day: yyyy/mm/dd, if 2024/7/15 -> 1
ans = (ans + d - 1) % 7;
return ans;
}
풀이 3
어떤 날자에 대한 요일 계산을 위에서 얘기한 첼러의 공식을 이용해서 해보자.
2024년 7월 15일을 가지고 공식을 설명해 보겠다.
- h는 요일을 나타내는 정수이다. (0:토, 1:일, 2:월, 3:화, 4:수, 5:목, 6:금) --> 위 풀이 1과 2에서와 다른 것에 유의
- q는 날자(day of month). 이 예제에서는 q=15
- m은 월을 나타내는데, 1월과 2월은 13, 14로 표현 (3:3월, 4:4월, ..., 12:12월, 13:1월, 14:2월). 여기서 m=7
- year는, 월이 1월과 2월의 경우는 year - 1을 하고, 나머지 달의 경우는 그대로 year사용한다. 예를 들어 2024년 1월 1일을 구할 경우는 year = 2023이고 m=13이 된다.
- K = year % 100. 2024년의 경우 K = 2024 % 100 = 24
- J = floor(year / 100) 2024의 경우 J = floor(2024/100) = 20
공식이 복잡해 보여도, 사실은 풀이 2에서 사용한 논리와 똑같다.
날자에 해당하는 q에 의한 요일 계산, 월에 대한 요일계산에 해당하는 13(m+1)/5, 연도에 의한 계산인 K + K/4 + J/4 - 2J
월에 대한 계산인 13(m+1)/5는, 각 월의 일수를 % 7한 것을 가지고, 해당 월까지의 일수합이 계산값이 floor를 하면 정확하게 떨어지도록 나누기 5를 교묘하게 한 것이다.
여하튼 위 공식을 구현하면 아래와 같다.
fn cal_weekaday2(year:usize, month:usize, day:usize) -> usize {
let q = day;
let m = if month <= 2 {month+12} else {month};
let k = if month <= 2 {(year-1) % 100} else {year % 100};
let j = if month <=2 {(year-1) / 100} else {year/100};
let mut t;
t = q + (13*(m+1)/5);
t += k;
t += k/4;
t += j/4;
t -= (2*j) % 7;
t = (t-1) % 7;
return t;
}공식의 항목을 풀어서 계산한 것은, 마지막 부분은 (2*j)를 빼는 부분이 있는데, 이에 의해 t가 음수가 되는 시점이 발생할 수 있고, 이렇게 되면 모든 변수를 usize가 아닌 i64로 바꿔서 계산해야 오류가 발생하지 않는다. 해서, 그냥 usize를 사용하기 위해서 스텝별로 계산하면서 (2*j) % 7을 해버림으로써 t에서 빼지는 값을 작게 만들어서 t가 음수가 되지 않도록 했다.
총평
간단하지만, 7을 법으로 한 계산을 생각해보게 하는 괜찮은 문제.
hackerrank에서는 year를 $10^{16}$까지 문제의 입력값으로 주기 때문에, 풀이 2에서와 같이 수식으로 요일을 계산하지 않는 한, 시간 내에 답을 내기가 쉽지 않다.
전체 소스코드
p19.rs
#[test]
fn test(){
assert_eq!(18, answer((1900,1,1), (1910,1,1)));
assert_eq!(35, answer((2000,1,1), (2020,1,1)));
assert_eq!(171, answer((1901,1,1), (2000,12,31)));
assert_eq!(0, answer((1900,7,31), (1901,1,1)));
}
#[cfg(test)]
fn answer((y1,m1,d1):(usize,usize,usize), (y2,m2,_d2):(usize,usize,usize)) -> usize{
let month = [0,31,28,31,30,31,30,31,31,30,31,30,31];
let mut ans:usize = 0;
let mut diff:usize = 1;
'outer: for y in 1900..=y2{
for m in 1..=12 {
if y == y2 && m >= m2 { break 'outer;}
diff += if is_leap(y) && m==2 {month[m]+1} else {month[m]};
if y < y1 || (y==y1 && m < m1) || (y==y1 && m==m1 && d1 > 1) {continue;}
if diff % 7 == 0 {ans += 1;}
}
}
return ans;
}
#[cfg(test)]
fn is_leap(y:usize) -> bool {
if y % 400 == 0 {return true;}
if y % 100 == 0 {return false;}
if y % 4 == 0 {return true;}
return false;
}
//-----------------
#[test]
fn test1(){
assert_eq!(6, cal_weekaday2(2000, 1, 1));
assert_eq!(1, cal_weekaday2(2024, 7, 15));
assert_eq!(1, cal_weekaday2(1900, 1, 1));
assert_eq!(6, cal_weekaday2(1908, 2, 1));
assert_eq!(6, cal_weekaday2(2000, 1, 1));
assert_eq!(2, cal_weekaday2(2000, 2, 1));
assert_eq!(3, cal_weekaday2(2000, 3, 1));
assert_eq!(18, answer1((1900,1,1), (1910,1,1)));
assert_eq!(35, answer1((2000,1,1), (2020,1,1)));
assert_eq!(171, answer1((1901,1,1), (2000,12,31)));
assert_eq!(6, answer1((1943,1,1), (1946,12,31)));
assert_eq!(10, answer1((1995,1,1), (2000,12,31)));
assert_eq!(0, answer1((1900,7,31), (1901,1,1)));
}
#[cfg(test)]
fn answer1((y1,m1,d1):(usize,usize,usize), (y2,m2,_d2):(usize,usize,usize)) -> usize{
let mut ans:usize = 0;
'outer: for y in y1..=y2{
for m in 1..=12 {
if y==y1 && (m<m1 || (m==m1 && d1>1)) {continue;}
if y==y2 && m>m2 {break 'outer;}
if cal_weekaday1(y,m,1)==0 {ans += 1;}
}
}
return ans;
}
#[cfg(test)]
// Monday: 1, ... Sat: 6, Sunday: 0
fn cal_weekaday1(y:usize, m:usize, d:usize) -> usize {
let mut ans:usize;
//1. year: yyyy/1/1, if 2024/1/1 -> 1
// 365 % 7 = 1, so y*365 = y
let yy = y - 1; //if y=4 --> have to consider only for 1~3
ans = (yy + (yy/4) - (yy/100) + (yy/400) + 1) % 7;
//2. month: yyyy/mm/1, if 2024/7/1 -> 1
let month = [0,0,31,59,90,120,151,181,212,243,273,304,334]; //x,x,Jan,Feb,Mar,...,Nov,0
ans = (ans + month[m]) % 7;
if (y%400==0 || (y%4==0 && y%100!=0)) && m > 2 {ans += 1;}
//3. day: yyyy/mm/dd, if 2024/7/15 -> 1
ans = (ans + d - 1) % 7;
return ans;
}
#[cfg(test)]
// Monday: 1, ... Sat: 6, Sunday: 0
fn cal_weekaday2(year:usize, month:usize, day:usize) -> usize {
let q = day;
let m = if month <= 2 {month+12} else {month};
let k = if month <= 2 {(year-1) % 100} else {year % 100};
let j = if month <=2 {(year-1) / 100} else {year/100};
let mut t;
t = q + (13*(m+1)/5);
t += k;
t += k/4;
t += j/4;
t -= (2*j) % 7;
t = (t-1) % 7;
return t;
}
끝
'Programming > Rust로 Euler 문제 풀이' 카테고리의 다른 글
| 020. Factorial Digit Sum (큰 수에 대한 팩토리얼 구하기) (1) | 2024.09.02 |
|---|---|
| [10번-19번] 문제에 대한 풀이 전체 코드 (0) | 2024.09.02 |
| 018. Maximum Path Sum I (삼각형 모양의 수 집단에서, 최대합이 되는 경로 찾기) (1) | 2024.09.02 |
| 017. Number Letter Counts (숫자를 영어로 읽었을 때, 몇 개의 문자가 되는지 구하기) (5) | 2024.09.02 |
| 016. Power Digit Sum ($2^{1000}$과 같은 큰 지수승 구하기) (0) | 2024.09.02 |
