취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 29543번 문제인 Smooth numbers이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/29543 

$(a_{i-1}+a_{i+1})/2\ge a_i$ 가 항상 성립해야 하므로 양 끝 자릿수가 아닌 $a_i$가 $a_{i-1}$에서 양수 $d$ 감소한 수라면 $a_{i_1}$은 $a_i$보다 $d$보다 덜 감소한 수여야 함을 관찰하자. 증가의 경우에도 이와 비슷한 관찰을 할 수 있다.

이 관찰에 따르면 하나의 수에서 감소가 4번 일어나려면 $a_1$에서 자릿수가 적어도 10은 떨어져야 함을 알 수 있다. 이는 10개의 자릿수밖에 없는 10진수에서는 가능하지 않으므로 하나의 수에서 연속한 감소는 많아야 3번 일어남을 알 수 있다. 이는 증가에서도 마찬가지로 적용된다. 물론 각 자리의 수가 증가하다가 감소(혹은 유지)해도 당연히 조건을 만족시키지 못한다.

위의 관찰을 토대로 가능한 경우의 답을 구해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	if (N == 1) cout << "9";
	else if (N == 2) cout << "99";
	else if (N == 3) cout << "989";
	else if (N == 4) cout << "9889";
	else if (N == 5) cout << "97679";
	else if (N == 6) cout << "976679";
	else if (N == 7) cout << "9643469";
	else if (N == 8) cout << "96433469";
	else cout << -1;
}