[백준] 24337 - 가희와 탑

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

24337번: 가희와 탑

 

사실 그리디 + 구성적, DP + 구성적 알고리즘이 제일 어려운 것 같다.

내가 생각하기에 최적의 해라고 생각해도, PS과정에서 증명하기엔 어려움이 있는 경우가 많기 때문이다.

이번 문제도 그렇다.

 

최소 빌딩의 높이는 1이고, 왼쪽, 오른쪽에서 보았을 때 각자 보이는 빌딩의 수가 주어진 뒤 빌딩 높이 수열에서 사전순으로 가장 앞서는 수열을 찾는 문제이다.

 

핵심은 두 가지이다.

1. 가능한 빌딩 수열 찾기

2. 사전순으로 가장 앞서게 만들기

 

사실 2번 같은 경우에는, 1번 조건을 해치지 않는 선에서, 빌딩의 최소 높이인 '1'을 계속 추가하는 것이다.

그렇다면 1번 조건을 만족해 보자.

즉, N을 신경 쓰지 않고 생각해 보자.

 

a = 4, b = 3이라 할 때 1 2 3 4 2 1

a = 3, b = 4이라 할 때 1 2 4 3 2 1

a = 5, b = 5이라 할 때 1 2 3 4 5 5 4 3 2 1

즉, 오름차순 이후에 내림차순으로 수를 있어나가면 된다.

1 ~ (a - 1) 만큼 i,

이후 max(a, b),

(b - 1) ~ 1 만큼 i

 

이렇게 하면 1번 조건을 만족시킬 수 있다.

2번 조건은 어떻게 만족해야 할까? 무작정 1만 앞에 추가하면 되는 것일까?

그렇지 않다.

 

N = 3, a = 1, b = 2에서 1번 조건으로 인해 만들어진 수열은 [2, 1]이다.

여기서 1을 맨 앞에 추가하면 [1, 2, 1]이다.

즉, 1번 조건을 해치지 않으려면 1번으로 만들어진 수열의 맨 처음 숫자 뒤에 '1'을 추가하는 것이다.

 

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

deque<int> d;

int main()
{
	int n, a, b;
	cin >> n >> a >> b;

	int highest = max(a, b);
	for (int i = 1; i < a; i++)
	{
		d.push_back(i);
	}
	d.push_back(highest);
	for (int i = b - 1; i >= 1; i--)
	{
		d.push_back(i);
	}
	if (d.size() > n)
	{
		cout << -1;
		return 0;
	}
	int first = d.front();
	d.pop_front();
	int dSize = d.size();
	for (int i = 1; i <= n - dSize - 1; i++)
	{
		d.push_front(1);
	}
	d.push_front(first);
	for (auto &i : d)
	{
		cout << i << ' ';
	}
}