[G3] 백준 24337번 가희와 탑 C++ 구현, 그리디 알고리즘, 해 구성하기

리뷰

 

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

왼쪽 끝과 오른쪽 끝에서 볼 수 있는 건물의 개수가 주어지고, 그 중 건물의 높이를 오름차순으로 정렬했을때 가장 앞에 있는 경우의 건물 높이를 출력해 주는 문제

구현 노가다로 AC를 받았는데 질문게시판의 반례를 많이 참고했다.

 

전역 변수

• n, a, b : 건물의 개수 n, 가희가 볼 수 있는 건물의 개수 a, 단비가 볼 수 있는 건물의 개수 b

 

함수

없음

 

 

문제풀이

1. n, a, b값을 입력 받고, 건물 높이를 출력할 정수형 벡터 result를 초기화 해준다.
2. temp를 n - a - b + 1로 초기화 해준다, 이는 볼 수 없는 건물은 모두 1로 처리해주기 위함이다.
3. 오름차순으로 출력해야 하는 문제로 a가 b보다 크거나 같거나 b가 더 큰 경우를 나누어서 구현해 주어야 한다.
4. a가 b보다 크거나 같은 경우 result에 1을 우선적으로 추가해 준다.
5. temp가 0보다 클 경우 result에 1을 temp만큼 추가해 준다.
6. 2 ~ a까지의 수를 result에 추가해 준 뒤 b - 1 ~ 1까지의 수를 result에 추가해 준다.
7. 만약 b가 a보다 클 경우 조건이 더 많아진다. 우선 flag를 false상태로 초기화 해준다.
8. a가 1보다 클 경우 result에 1을 추가해 주고, flag를 1로 변경해준다.
9. a가 1일 경우엔 result에 b를 추가해 준다.
10. 마찬가지로 temp가 0보다 크다면 result에 temp만큼 1을 추가해 준다.
11. 2 ~ a - 1까지 result에 추가해 준다.
12. flag가 1이면 b ~ 1까지 result에 추가, flag가 0이라면 b - 1 ~ 1까지 result에 추가해 준다.
13. 모든 작업을 마치고 만약 result의 size가 n이 아니라면 -1을 출력해 준다.
14. n과 result의 size가 동일하다면 result에 저장된 값들을 공백을 기준으로 순차적으로 출력해 준다.

 

참고 사항

• a >= b 일땐 우선 1을 추가하고, temp만큼 1을 추가해주면 자동적으로 오름차순이 만들어 진다.
• a < b 일땐 a가 1인 경우 b가 먼저와야하고, a가 1보다 크다면 1이 제일 먼저 오는것이 오름차순을 만들 수 있다.
• https://www.acmicpc.net/board/view/134211 해당 링크의 반례 모음이 큰 도움이 되었다.

 

정답 코드

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

int n, a, b;

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

	cin >> n >> a >> b;
	vector<int> result;

	int temp = n - a - b + 1;
	if (a >= b) {
		result.push_back(1);
		while (temp-- > 0) result.push_back(1);
		for (int i = 2; i <= a; i++) result.push_back(i);
		for (int i = b - 1; i > 0; i--) result.push_back(i);
	}
	else {
		int flag = 0;
		if (a > 1) {
			result.push_back(1);
			flag = 1;
		}
		else result.push_back(b);
		while (temp-- > 0) result.push_back(1);
		for (int i = 2; i < a; i++) result.push_back(i);
		if (flag) for (int i = b; i > 0; i--) result.push_back(i);
		else for (int i = b - 1; i > 0; i--) result.push_back(i);
	}

	if (result.size() == n) for (int i : result) cout << i << " ";
	else cout << -1;
}