[백준][C++] 19230: Datum

문제 링크: https://www.acmicpc.net/problem/19230

 

음;; 일단 이렇게 푸는 문제인지 잘 모르겠습니다. 어거지로 풀었다는 생각이 듭니다. 그 점 감안해서 봐주세요

입력으로 날짜가 DD.MM.YYYY. 형태로 주어지고 이 날짜 이후 팰린드롬 날짜를 구해 출력해야 합니다.

팰린드롬 날짜란 날짜가 DDMMYYYY 형태일 때 뒤로 읽어도 똑같은 날짜를 말합니다. 예를 들어 2020년 2월 3일 (03.02.2020.)은 팰린드롬 날짜가 아니고, 121년 10월 12일 (12.10.0121.)은 팰린드롬 날짜입니다.

 

팰린드롬 날짜를 찾는 방법은 그냥 브루트포스입니다. 팰린드롬 날짜가 나올 때까지 계속 다음날짜로 넘어갑니다. 팰린드롬 날짜가 나오면 그 날짜를 DD.MM.YYYY. 형식으로 출력하면 끝입니다.

그런데 이렇게만 하면 시간초과가 나옵니다.

 

생각해보면 날짜 처음과 끝까지 팰린드롬 날짜만 미리 구해놓은 다음, 날짜를 입력받으면 그 날짜 다음 팰린드롬 날짜를 구할 수 있습니다. 무조건 YYYY 포맷으로 출력할 수 있는 날짜만 입력으로 들어오니 0001~9999년까지 전부 구해보면 되겠습니다. 참고로 이 문제에서 윤년은 4의 배수 연도입니다.

참고로 팰린드롬 날짜를 전부 구해보면 처음은 101년 10월 10일 (10.10.0101), 마지막은 9092년 9월 29일 (29.09.9092.)가 됩니다. 개수는 366개네요.

 

입력되는 날짜를 이용해 그 날짜 이후 팰린드롬 날짜를 어떻게 구할까요? 팰린드롬 날짜를 구할 때 YYYYMMDD 형식 string으로 vector에 저장해놓으면 자동으로 오름차순으로 들어가게 됩니다.

입력을 다시 YYYYMMDD 형태로 수정한 뒤 upper_bound를 써서 바로 다음 팰린드롬 날짜를 구하면 완성입니다.

 

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING
#include <bits/stdc++.h>
using namespace std;


const int MONTH_DAYS[] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

constexpr bool leap_year(int y) {
	// 이 문제 전용
	return (y%4)==0;
}

bool is_palindromic(int d, int m, int y) {
	string s = string(d<10, '0') + to_string(d) + string(m<10, '0') + to_string(m);
	string y_rev = to_string(y);
	y_rev = string(4 - y_rev.size(), '0') + y_rev;

	reverse(y_rev.begin(), y_rev.end());

	return y_rev == s;
}

void next_day(int& d, int& m, int& y) {
	++d;
	if ((leap_year(y) && m==2 && d==MONTH_DAYS[1]+2)
		|| (!leap_year(y) && m==2 && d==MONTH_DAYS[1]+1)
		|| (m!=2 && d==MONTH_DAYS[m-1]+1)) {
		d = 1;
		++m;

		if (m == 13) {
			m = 1;
			++y;
		}
	}
}

// YYYYMMDD
string day_to_str(int d, int m, int y) {
	string sd = to_string(d), sm = to_string(m), sy = to_string(y);

	string s = string(4 - sy.size(), '0') + sy
		+ string(2 - sm.size(), '0') + sm
		+ string(2 - sd.size(), '0') + sd;

	return s;
}


int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif

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

	int n;
	char c;


	vector<string> palindromic_dates;

	int dd = 10, mm = 10, yy = 101;
	while (yy<9093) {
		if (is_palindromic(dd, mm, yy)) {
			palindromic_dates.push_back(day_to_str(dd, mm, yy));
		}

		next_day(dd, mm, yy);
	}

	cin >> n;
	while (n--) {
		int d, m, y;
		cin >> d >> c >> m >> c >> y >> c;

		string s = day_to_str(d, m, y);
		auto it = upper_bound(palindromic_dates.begin(), palindromic_dates.end(), s);
		cout << it->substr(6, 2) << "." << it->substr(4, 2) << "."
			<< it->substr(0, 4) << ".\n";
	}

	return 0;
}

대충 짠 코드입니다

실행시간이 800ms 정도로 약간 아슬아슬하게 통과가 됩니다.