[백준 24337번 C/C++] 가희와 탑

 

[백준 24337번 C/C++] 가희와 탑

 

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

 

24337번: 가희와 탑

일직선으로 다양한 높이의 건물들이 N개 존재합니다. 가희는 건물들의 왼쪽에, 단비는 건물들의 오른쪽에 있습니다. 일직선 상에 가희와 단비, 건물들은 아래와 같은 순서로 배치되어 있습니다.

www.acmicpc.net

---

 

 

해결전략

 

그리디 Greedy Algorithm

 

1. 가장 높은 빌딩의 높이 계산
   • int tallest = max(a, b);
   • 가희와 단비 중 더 많은 건물을 볼 수 있는 사람이 볼 수 있는 가장 높은 건물의 높이를 결정한다. 이는 두 관점에서 공통적으로 보이는 가장 높은 건물이 된다.
2. 건물 배치
   • 가희와 단비 각각의 관점에서 볼 수 있는 건물들을 v1과 v2에 배치
   • 가희의 관점(v1): 가희가 볼 수 있는 건물의 수만큼 루프를 돌며, 가장 마지막에 가장 높은 건물을 배치
   • 단비의 관점(v2): 단비가 볼 수 있는 건물의 수만큼 역순으로 루프를 돌며, v2에 건물을 배치
3. 전체 건물 개수와의 비교
   • 만약 가희와 단비의 관점에서 볼 수 있는 건물의 총 개수가 n보다 많다면, 문제의 조건을 만족할 수 없으므로 -1을 출력하고 프로그램을 종료
4. 추가로 들어갈 건물 계산 및 배치
   • 만약 n이 가희와 단비의 관점에서 볼 수 있는 건물의 총 개수보다 크다면, 추가로 들어갈 수 있는 건물의 개수를 계산한다.
   • 추가로 들어갈 건물이 없는 경우, v1과 v2에 저장된 건물들을 순서대로 출력한다.
   • 추가로 들어갈 건물이 있는 경우, 가희가 볼 수 있는 건물이 한 개밖에 없다면 추가 건물을 v1과 v2 사이에 배치합니다. 그렇지 않다면 추가 건물을 v1 앞에 배치한다.

---

 

 

정답코드

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int n; // 전체 건물의 개수
int a, b; // 가희, 단비 각각 볼 수 있는 건물의 개수
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	cin >> n >> a >> b;
 
	vector<int> v1, v2;
 
	int tallest = max(a, b); // 가장 높은 빌딩의 높이
 
	// 가희(왼쪽) 기준 빌딩 배치
	for(int i = 1; i <= a; i++){
		if (i == a)
			v1.push_back(tallest);
		else
			v1.push_back(i);
	}
 
	// 단비(오른쪽) 기준 빌딩 배치
	for(int i = b - 1; i >= 1; i--){
		v2.push_back(i);
	}
 
	// 가희와 단비 기준으로 만족하는 빌딩 배치 시 필요한 건물이 전체 건물의 개수 보다 더 많은 경우 
	if (v1.size() + v2.size() > n) {
		cout << "-1";
		return 0;
	}
 
	// 만족하는 빌딩 배치 조건 외 추가로 들어갈 건물 수 구하기
	int additional = n - (v1.size() + v2.size());
 
	if (additional == 0){ // 추가로 들어갈 건물이 없다면
		for(int i = 0; i < v1.size(); i++)
			cout << v1[i] << " ";
		for (int i = 0; i < v2.size(); i++) 
			cout << v2[i] << " ";
	}
	else{ // 추가로 들어갈 건물이 있다면
		if(a <= 1){
			for (int i = 0; i < v1.size(); i++)
				cout << v1[i] << " ";
			for (int i = 0; i < additional; i++)
				cout << "1 ";
			for (int i = 0; i < v2.size(); i++)
				cout << v2[i] << " ";			
		}
		else{
			for (int i = 0; i < additional; i++)
				cout << "1 ";
			for (int i = 0; i < v1.size(); i++)
				cout << v1[i] << " ";
			for (int i = 0; i < v2.size(); i++)
				cout << v2[i] << " ";			
		}
	}
 
	return 0;
}

 

 

---