💬 Comment
- 어떻게 하면 증가하는 관계로 만들 수 있을까? → 인접한것들끼리 먼저 성립해야 한다
- 인접한 원소들끼리 증가하는 관계가 성립 → 전체의 증가하는 관계성립
부분 문제의 최적결과가 전체에도 그대로 적용locally optimal choice → globally optimal solution⇒ Greedy
⏰ 시간복잡도
-
레벨의 갯수 N 이 최대 100
-
input을 위한 시간복잡도 → O(N)
-
이중 for문 → O(N*N)
👉 O(N*N)
📝 문제이해를 위한 메모
# 1초 / 128MB
# 게임에 N개의 레벨
# -> 각 레벨 클리어할때마다 "점수"
# 플레이어점수 = 각 레벨 클리어하면서 얻은 점수들의 합
# 이 점수로 -> 순위 매김
# Condition
# 레벨을 난이도 순으로 배치
# 쉬운레벨의 점수 > 어려운 레벨 점수
# Purpose>
# 특정 레벨의 점수를 감소시키려고 함
# => 클리어할때마다, 점수가 증가하도록
# Output>
# 몇 번 감소시키면 되는지
# 항상 답이 존재 !
# 정답이 여러가지 -> 점수내리는 것을 "최소한"으로..🥳 정답
# Input>
N = int(input()) # 레벨의 수 / 1이상, 100이하
score = []
for n in range(N):
# 레벨 클리어하면 얻는 점수들 / 1이상 20,000이하 정수
score.append(int(input()))
down_cnt = 0 # 몇 번 감소시키면 되는지 카운트 하는 변수
for i in range(N-1):
for j in range(N-1):
if score[j] >= score[j+1]:
tmp = (score[j] - score[j+1]) + 1
score[j] -= tmp
down_cnt += tmp
# Output
print(down_cnt)