boj, 백준) 1138 한줄로서기 (C++)

1. 문제 링크

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

1138번: 한 줄로 서기

2. 문제 개요

 왼쪽에 자기보다 키 큰 사람의 수를 알 때, 서 있는 순서 계산하기.

 

3. 문제 힌트!!

 

1) DFS 전수 조사하기(순열).

1-1) Backtracking 사용할 것.

 

2) 키가 큰 사람부터 줄 세우기(Greedy)

 

4. 문제 풀이

 

1) DFS를 사용한 백트래킹은 생략. -> 순열 만들어서 주어진 입력을 만족하는지 check 하면 됨. -> 약 100ms

 

2) Greedy

 입력  4 / 2 1 1 0을 예로 들면,

1번은 자기보다 키 큰 사람이 2명, 2번은 1명, 3번은 1명, 4번은 0명이다.

 

문제의 답이 될 줄을 하나의 Vector로 선언하고 키가 큰 순서대로 줄 세운다.

4번 사람 0 ->0번 index에 insert.

답 Vector : 4

 

3번 사람 1-> 1번 index에 insert.

답 Vector : 4 3

 

2번 사람 1 -> 1번 index에 insert.

답 Vector : 4 2 3

 

1번 사람 2 -> 2번 index에 insert.

답 Vector : 4 2 1 3

 

따라서 정답은 4 2 1 3이 된다.

 

 

5. 코드

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

vector <int> sol;
int order[10];

int main()
{
	int n;

	cin >> n;

	for (int i = 0; i < n; ++i)
		cin >> order[i];

	

	for (int i = n - 1; i >= 0; --i)
	{
		vector<int>::iterator iter = sol.begin();
		for (int k = 0; k < order[i]; ++k)
			iter++;

		sol.insert(iter, i + 1);
	}

	for (int i = 0; i < sol.size(); ++i)
		cout << sol[i] << " ";
	return 0;
}

지적, 댓글 언제나 환영입니다~