[Baekjoon][C++] 1476번 날짜계산 문제설명 및 코드

1476번: 날짜 계산

▷ 문제설명

준규가 사는 나라는 연도를 표현할 때 E, S, M 세 문자로 표현한다.

각각의 문자가 가지는 범위는 1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19 이다.

E, S, M이 주어질 때,  E S M으로 표시되는 가장 빠른 연도를 출력하자.

 

▷ 문제풀이

이 문제의 경우 표현할 수 있는 년도는 15 * 28 * 19 = 7980년까지 이므로

브루트포스 방법으로 1년 부터 7980년까지 구하다가 정답과 같아지는 순간을 찾으면 된다.

 

이 때, 문제에서 주어진 E, S, M의 값은

year mod 15 = E,

year mod 28 = S,

year mod 19 = M 를 나타내므로(나머지 값)

 

1년 부터 7980년까지 연도를 증가시킬 때,

현재 연도 year를 year % 15 && year % 28 && year % 19 로 계산했을 때,

그 값들이 주어진 E, S, M의 값과 모두 일치한다면 현재의 연도가 정답 연도이다.

 

▷ 시간복잡도

표현할 수 있는 년도를 N이라 하면, N가지의 경우의 수가 필요하므로 O(N)의 시간복잡도를 갖는다.

 

▷ 정답코드

#include <iostream>
using namespace std;

void Input();
void CalculateYear(int E, int S, int M);

int main() {
	Input();
	return 0;
}

void Input() {
	int E, S, M;
	cin >> E >> S >> M;
	CalculateYear(E, S, M);
}

void CalculateYear(int E, int S, int M) {
	int e = 1, s = 1, m = 1;
	for (int year = 1; ; year++) {
		if (e % 15 == E % 15 &&
			s % 28 == S % 28 &&
			m % 19 == M % 19){
			cout << year;
			break;
		}e++, s++, m++;
	}
}