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

https://www.acmicpc.net/problem/24337
24337번: 가희와 탑
일직선으로 다양한 높이의 건물들이 N개 존재합니다. 가희는 건물들의 왼쪽에, 단비는 건물들의 오른쪽에 있습니다. 일직선 상에 가희와 단비, 건물들은 아래와 같은 순서로 배치되어 있습니다.
www.acmicpc.net
해결전략
그리디 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
댓글을 사용할 수 없습니다.