[백준 24337번 C/C++] 가희와 탑
[백준 24337번 C/C++] 가희와 탑
https://www.acmicpc.net/problem/24337
해결전략
그리디 Greedy Algorithm
- 가장 높은 빌딩의 높이 계산
- int tallest = max(a, b);
- 가희와 단비 중 더 많은 건물을 볼 수 있는 사람이 볼 수 있는 가장 높은 건물의 높이를 결정한다. 이는 두 관점에서 공통적으로 보이는 가장 높은 건물이 된다.
- 건물 배치
- 가희와 단비 각각의 관점에서 볼 수 있는 건물들을 v1과 v2에 배치
- 가희의 관점(v1): 가희가 볼 수 있는 건물의 수만큼 루프를 돌며, 가장 마지막에 가장 높은 건물을 배치
- 단비의 관점(v2): 단비가 볼 수 있는 건물의 수만큼 역순으로 루프를 돌며, v2에 건물을 배치
- 전체 건물 개수와의 비교
- 만약 가희와 단비의 관점에서 볼 수 있는 건물의 총 개수가 n보다 많다면, 문제의 조건을 만족할 수 없으므로 -1을 출력하고 프로그램을 종료
- 추가로 들어갈 건물 계산 및 배치
- 만약 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;
}
'⭐ 코딩테스트 > 백준' 카테고리의 다른 글
[백준 14890번 C/C++] 경사로 (0) | 2024.04.13 |
---|---|
[백준 8980번 C/C++] 택배 (0) | 2024.04.10 |
[백준 2931번 C/C++] 가스관 (1) | 2024.04.08 |
[백준 17825번 C/C++] 주사위 윷놀이 (0) | 2024.04.03 |
[백준 17136번 C/C++] 색종이 붙이기 (0) | 2024.03.26 |
댓글
이 글 공유하기
다른 글
-
[백준 14890번 C/C++] 경사로
[백준 14890번 C/C++] 경사로
2024.04.13 -
[백준 8980번 C/C++] 택배
[백준 8980번 C/C++] 택배
2024.04.10 -
[백준 2931번 C/C++] 가스관
[백준 2931번 C/C++] 가스관
2024.04.08 -
[백준 17825번 C/C++] 주사위 윷놀이
[백준 17825번 C/C++] 주사위 윷놀이
2024.04.03