[79일차][백준][누적합][2851]슈퍼 마리오

문제 설명

슈퍼 마리오 앞에 10개의 버섯이 일렬로 놓여져 있다. 이 버섯을 먹으면 점수를 받는다.

슈퍼 마리오는 버섯을 처음부터 나온 순서대로 집으려고 한다. 하지만, 모든 버섯을 집을 필요는 없고 중간에 중단할 수 있다. 중간에 버섯을 먹는 것을 중단했다면, 그 이후에 나온 버섯은 모두 먹을 수 없다. 따라서 첫 버섯을 먹지 않았다면, 그 이후 버섯도 모두 먹을 수 없다.

마리오는 받은 점수의 합을 최대한 100에 가깝게 만들려고 한다.

버섯의 점수가 주어졌을 때, 마리오가 받는 점수를 출력하는 프로그램을 작성하시오.

 

입력

총 10개의 줄에 각각의 버섯의 점수가 주어진다. 이 값은 100보다 작거나 같은 양의 정수이다. 버섯이 나온 순서대로 점수가 주어진다.

 

출력

첫째 줄에 마리오가 받는 점수를 출력한다. 만약 100에 가까운 수가 2개라면 (예: 98, 102) 마리오는 큰 값을 선택한다.

 

예제 입력, 예제 출력

10 20 30 40 50 60 70 80 90 100	100
1 2 3 5 8 13 21 34 55 89	87
40 40 40 40 40 40 40 40 40 40	120

 

 

코드 및 설명

import sys

mushroom = 10
prefix_sum = [0] * int(mushroom+1)

for idx in range(1, mushroom+1):
  score = int(sys.stdin.readline())
  prefix_sum[idx] = prefix_sum[idx-1] + score
    
  if prefix_sum[idx] >= 100:
    pre_check = 100 - prefix_sum[idx-1]
    next_check = prefix_sum[idx] - 100
    
    if pre_check == next_check:
      print(prefix_sum[idx])
    elif pre_check < next_check:
      print(prefix_sum[idx-1])
    else:
      print(prefix_sum[idx])      
    break
  
  if idx == mushroom and prefix_sum[len(prefix_sum)-1] < 100:
    print(prefix_sum[len(prefix_sum)-1])

 

이 문제는 누적합으로 풀면 된다. 대신 답을 구하는 조건들이 있는 데, 

일단 버섯의 개수는 10개

1개 먹을 때마다 점수가 합쳐진다.

총 10개의 버섯을 먹을 수 있으며 100점을 넘으면 

 

1. 100에 가까운 수가 98, 102 라면 큰 수로 

2. 100을 넘었을 때 100에 가까운 수를 채택

 

하나하나 점수를 받아가며, prefix_sum에 담고 이게 100을 넘어가는 시점이 오면

이전 합과 이후 합을 100으로 빼고 두 수를 비교한다. 같으면 prefix_sum[idx]

pre_check가 더 작으면  prefix_sum[idx-1]

그게 아니라면  prefix_sum[idx]

그리고 break를 걸어준다.

 

근데 한가지 봐야할 것이 버섯 10개를 다 먹었는 데도 100이 안 됐을 때를 체크해야 한다.

idx가 mushroom과 같아 지고, prefix_sum의 마지막 배열이 값이 100보다 작으면 prefix_sum의 마지막 배열을 출력해주면 된다!!!