Problem #019

오일러 알고리즘

🚩 문제 설명

오일러 알고리즘 #019

◾ 20세기에서 매월 1일이 일요일인 경우는 몇번인가 구하는 문제

◾ 달력에 관한 기본적인 정보들이 주어진다.

◾ 1900년은 1월 1일은 월요일이다.

◾ 4/6/9/11월은 30일까지

◾ 1/3/5/7/8/10/12월은 21일까지 있다.

◾ 2월은 28일까지, 윤년은 29일까지 있다.

◾ 1901년에서 2000년까지 셈을 센다.

윤년이란?
연도가 4로 나누어지는 해를 이른다.
하지만 400으로 나누어 떨어지지 않는 100년째는 윤년이 아니며,
400으로 나누어 떨어지면 윤년이다.

 

 

---

 

 

📑 문제 풀이

#include <iostream>
#include <ctime>
using namespace std;

string week[7] = {"mon", "tue", "wed", "thr", "fri", "sat", "sun"};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	clock_t start, end;
	start = clock();

	int day = 1;
	string ThisWeek = "tue";
	int idx = 1;
	int cnt = 0;		// 1일이자 일요일인 날을 센다

	for (int i = 1901; i <= 2000; i++)
	{
		for (int j = 1; j <= 12; j++)
		{
			if (j == 1 || j == 3 || j == 5 || j == 7 || j == 8 || j == 10 || j == 12)
			{
				day += 31;
				idx = idx + ((day % 7) - 1);
				ThisWeek = week[idx%7];
				if (ThisWeek == "sun") cnt++;
				day = 1;
			}
			else if (j == 4 || j == 6 || j == 9 || j == 11)
			{
				day += 30;
				idx = idx + ((day % 7) - 1);
				ThisWeek = week[idx%7];
				if (ThisWeek == "sun") cnt++;
				day = 1;
			}
			else
			{
				if (i % 4 == 0 && i % 100 != 0 || i % 400 == 0)		// 윤년 처리
				{
					day += 29;
					idx = idx + ((day % 7) - 1);
					ThisWeek = week[idx % 7];
					if (ThisWeek == "sun") cnt++;
					day = 1;
				}
				else
				{
					ThisWeek = ThisWeek;
					if (ThisWeek == "sun") cnt++;
					day = 1;
				}
			}
		}
	}

	end = clock();

	cout << "시간:" << (double)(end - start)/CLOCKS_PER_SEC << '\n';
	cout << cnt << '\n';

	return 0;
}

💬 Point

👉 요일 배열을 만들어줬다.
👉 일수를 이용하여 day % 7 로 하여 해당 요일을 구한다.

◾ 첫번째 반복문은 1901년에서 2000년까지 돈다.

◾ 두번째 반복문은 월을 뜻하며 1월에서 12월까지 돈다.

◾ day 변수를 이용해서 요일 배열의 인덱스를 구한다.

◾ 인덱스는 day % 7 - 1로 구할 수 있다.

• 7로 나눠주는 이유는 요일은 7일이 기준이기 때문이다.
• 1일이 만약에 월요일이었다면, 1 + 7 = 8 이고
• 8일은 월요일이다.
• -1 을 해주는 이유는 배열이 0부터 시작하기 때문이다.

◾ 각자 월마다 한달의 일수를 더해줘야한다.

◾ 그래서 한달 일수가 다른 월을 기준으로 조건문을 넣어준다.

◾ ThisWeek가 일요일이라면 카운트를 해준다.

◾ 윤년처리도 해준다.

 

 

---

 

 

But,

✅ 조건문 안에 있는 식을 좀 더 간편하게 짤 수 있었을 것이다.
✅ 굳이 idx 라든지 변수를 추가하지않고 day 하나로도 구할 수 있었을 것이다.
✅ 너무 복잡하게 생각한 것 같다.

➕ 풀이 사이트 첨부

https://www.mathblog.dk/project-euler-19/

Project Euler 19: How many Sundays on the first of a month in C# | MathBlog

 

 

 

 

 

 

 

 

 

 

 

 

---