[BOJ 25287] 백준 25287번 - 순열 정렬

		제6회 천하제일 코딩대회 예선 풀이
A		[BOJ 25285] 심준의 병역판정검사
B		[BOJ 25286] 11월 11일
C		[BOJ 25287] 순열 정렬
D		[BOJ 25288] 영어 시험
E		[BOJ 25289] 가장 긴 등차 부분 수열

1. 문제

$25287$. 순열 정렬 (제6회 천하제일 코딩대회 예선 C번)

백준 25287번 - 순열 정렬 (https://www.acmicpc.net/problem/25287)

2. 풀이

감소하지 않는 수열을 만들 수 있는지 판별하는 문제이므로, 최선을 다해 수열을 완성해야 한다. 앞의 수의 값이 작으면 작을수록, 그 다음 수의 선택 범위가 넓어진다. 따라서, 앞에서부터 최대한 작은 수를 선택하는 것이 greedy한 방법임을 알 수 있다.

특정 index에서 가능한 수는 arr[i]와 N - arr[i] + 1 두 개가 있다. 이 둘 중, 이전 수보다 크거나 같은 최솟값을 선택하면 된다.

도중에 선택에 실패하면(두 수가 모두 이전 수보다 작으면 선택에 실패한다), NO를 출력하고, 전부 성공하면 YES를 출력한다.

3. 채점 결과

4. 회고

.

5. 코드