문제 바로가기
문제 풀이
키가 작은 순서대로 입력, answer를 [0]*N의 list로 만들었을 때, 0의 수가 현재 사람이 기억하는 자기보다 큰 사람의 수와 같아야 성립한다.
-> 본인보다 큰 사람이 있을 경우를 고려했기 때문에 계속해서 오류가 발생
정답 코드
"""
https://www.acmicpc.net/problem/1138
"""
n = int(input())
line = list(map(int, input().split()))
answer = [0] * n
for i in range(1, n + 1):
temp = line[i - 1]
cnt = 0
for j in range(n):
if temp == cnt and answer[j] == 0:
answer[j] = i
break
elif answer[j] == 0:
cnt += 1
print(*answer)추가적인 개념 (optional)
greedy algorithm
→ 미래를 생각하지 않고, 현재 상황에서 가장 최선인 선택을 선택하는 것 / 현재 상황에서 최선인 것들의 집합이 반드시 최종적인 해답에서의 최적의 값이라는 보장은 할 수 없다.
- 문제를 해결하는 방법 : 현재 상황에서의 최선의 선택 → 선택이 문제의 조건을 만족하는지 검사 → 원래의 문제가 해결되었는지 검사, 해결되지 않았다면 선택으로 돌아가 위의 과정을 반복
- 근사 알고리즘으로 사용할 수 있으며, 대부분의 경우 계산 속도가 빠르기 때문에 실용적이다.
동적 프로그래밍과 비슷하나 훨씬 더 효율적이다. 그러나 최적의 값을 항상 만족하는 것은 아니기 때문에 보완하는 개념으로 알려진다.
