728x90
시간 제한 : 2초
메모리 제한 : 128MB
입력
첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i-1보다 작거나 같다.
출력
첫째 줄에 줄을 선 순서대로 키를 출력한다.
소스코드
#include <iostream> using namespace std; int main(void) { int n; int arr[10], ans[11] = { 0, }; cin >> n; for (int i = 0; i < n; i++) cin >> arr[i]; ans[arr[0] + 1] = 1; for (int i = 1; i < n; i++) { int cnt = 0; for (int j = 1; j <= n; j++) { if (cnt == arr[i] && ans[j] == 0) { ans[j] = i + 1; break; } if (ans[j] > i + 1 || ans[j] == 0) cnt++; } } for (int i = 1; i <= n; i++) cout << ans[i] << ' '; }
Tip
어느 시점에 사람을 배치해야 하는지 애를 조금 먹었는데, 주어진 숫자(자기보다 키가 큰 사람의 숫자)와 같아지는 순간에 배치하려는 곳이 공석이면 바로 배치하는 식으로 접근하면 된다. 조건을 충족하는대로 바로 배치하는 점에서 그리디로 분류한 듯. 수학적으로 접근하는 방법은 잘 모르겠다.
728x90
'Computer Science > Algorithm Problem' 카테고리의 다른 글
백준] 2512 - 예산(KOI 2012;한국정보올림피아드 2012) (0) | 2018.06.12 |
---|---|
백준] 14470 - 전자레인지(JOI 2017 예선) (0) | 2018.06.10 |
백준] 1812 - 사탕 (0) | 2018.06.07 |
백준] 1439 - 뒤집기 (0) | 2018.06.06 |
백준] 1531 - 투명 (0) | 2018.06.05 |