[구현] 백준 2847: 게임을 만든 동준이 (Python)

임동혁 Ldhbenecia·2023년 8월 26일

구현 백준 알고리즘

Algorithm

목록 보기

2/16

BOJ 2847 게임을 만든 동준이

실버4라고 얕봤다가 피를 본 문제입니다..

정답 코드

n = int(input())
score_list = [int(input()) for _ in range(n)]
cnt = 0

for i in range(n - 1, 0, -1):
  if score_list[i] <= score_list[i - 1]:
    minus_value = score_list[i - 1] - score_list[i] + 1 # 이전 값이랑 비교해서 1 큰거
    cnt += minus_value
    score_list[i - 1] = score_list[i] - 1 # 이전 값 변경
    
print(cnt)

풀이과정

3 5 5가 주어졌다고 가정하면

3 4 5가 되어야합니다.
거꾸로 반복문을 돌면서 시작합니다.

최대 레벨의 점수가 5

그 이전 값의 점수가 5인 경우

4가 되어야합니다.
한칸 앞칸의 값과 1 차이가 나야합니다.
그러므로 이전 값에서 한칸 앞의 값을 뺀 후 + 1 처리
5 - 5 + 1이 나와서
1번 감소하면 4가 나옵니다.

이 값은 변경되는 값이므로 몇 번 감소되었는지를 뜻합니다.

그 이후 이전 값을 맞춰서 4로 변경해주면됩니다.
그 이전 값의 점수가 6인 경우

4가 되어야합니다.
한칸 앞칸의 값과 1차이가 나야합니다.
그러므로 이전 값에서 한칸 앞의 값을 뺀 후 + 1처리
위와 동일함 6 - 5 + 1 = 2가 나와서
2번 감소하면 4가 나옵니다.

이 외의 상황은 한칸 앞의 코드를 변경을 시켜주기 때문에 고려할 필요가 사라집니다.

주의해야할 점

1 4 5가 주어졌을 경우에 대해서 생각을 해보겠습니다.
문제 이해가 중요한데 3 4 5를 만들어야하는 문제가 아닙니다.

낮은 레벨의 문제의 점수가 높은 레벨의 점수보다 높지만 않으면 되기 때문에
1 4 5가 나왔을 경우 이대로 끝나서 정답은 0이 됩니다.

1 6 5가 나왔을 경우
위의 코드 상에서 돌아가서 1 4 5가 나옵니다.

그래서 코드에서 이전 값이 현재 값보다 크거나 같을 경우만 체크를 하고
이전 값이 작을 경우는 고려할 필요가 사라진다는 뜻입니다.

오답 코드 (처음에 풀이했던 코드)

n = int(input())
score_list = [int(input()) for _ in range(n)]
cnt = 0

for i in range(len(score_list)):
  max_level_score = score_list[-1]
  max_level_idx = score_list.index(score_list[-1])
  last_level_index = len(score_list) - 1 # 제일 마지막 레벨 인덱스
  
  save_value = score_list[i]
  
  if score_list[i] == max_level_score:
    minus_value = last_level_index - i # 빼야할 값
    score_list[i] = score_list[i] - minus_value
    cnt += minus_value
    
  elif score_list[i] > max_level_score:
    score_list[i] = score_list[i - 1] + 1
    minus_value = save_value - score_list[i]
    cnt += minus_value
  
  elif score_list[i] < max_level_score:
    change_value = score_list[i + 1] - 1
    minus_value = change_value - score_list[i]
    cnt += minus_value

print(cnt)

# 레벨 1 2 3
# 3점 5점 5점
# 3점 4점 5점 -> 0 1 0 -> 1번

# 레벨 1 2 3
# 1점 4점 5점
# 3점 4점 5점 -> 2 0 0 -> 2번


# 레벨 1 2 3
# 5점 5점 5점
# 3점 4점 5점 -> 2, 1, 0

# 레벨 1 2 3 4
# 5점 3점 7점 5점
# 2점 3점 4점 5점 -> 3, 0, 3, 0

# 1. 만약 최대레벨과 점수가 같다면
# 최대 레벨 인덱스 - 현재 레벨 인덱스 = 빼야할 값
# 2. 만약 최대레벨보다 크다면 현재 이전 값보다 1만 크면 됨
# 최대레벨보다 큰 값 - 이전 값보다 1만 커진값 = 빼야할 값

# 빼야할 값만큼 cnt에 더하면 몇번 뺐는지 확인 가능