BOJ 2851번 : 슈퍼 마리오 (Python/Bronze 1)

2851번: 슈퍼 마리오

문제

슈퍼 마리오 앞에 10개의 버섯이 일렬로 놓여져 있다. 이 버섯을 먹으면 점수를 받는다. 슈퍼 마리오는 버섯을 처음부터 나온 순서대로 집으려고 한다. 하지만, 모든 버섯을 집을 필요는 없고 중간에 중단할 수 있다. 중간에 버섯을 먹는 것을 중단했다면, 그 이후에 나온 버섯은 모두 먹을 수 없다. 따라서 첫 버섯을 먹지 않았다면, 그 이후 버섯도 모두 먹을 수 없다. 마리오는 받은 점수의 합을 최대한 100에 가깝게 만들려고 한다. 버섯의 점수가 주어졌을 때, 마리오가 받는 점수를 출력하는 프로그램을 작성하시오.

 

입력

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

 

출력

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

---

예제 입력

1
2
3
5
8
13
21
34
55
89

예제 출력

87

---

설명

점수가 부여된 10개의 버섯이 있다. 순서대로 집어 먹는데 100점에 가까운 점수가 되어야 한다. 단, 먹다가 멈출 순 있지만 멈춘 이후로는 먹지 못한다. 

 

풀이

- 누적 합 이용

 

누적 합 구하는 코드

array = [10, 20, 30, 40, 50]
n = len(array)
prefix_sum = [0] * (n + 1)

for i in range(n):
    prefix_sum[i + 1] = prefix_sum[i] + array[i]
   
 결과 : prefix_sum[0, 10, 30, 60, 100, 150]

누적 합 알고리즘 설명 - https://dev-cloud.tistory.com/141

주의 사항

- 100에 가까운 수가 두 개면 큰 값을 출력해야 한다.

- 버섯의 누적 합계가 100이상이 된다는 보장이 없다. 

Solution

n = []
for _ in range(10):
    n.append(int(input()))
    
prefix_sum = [0]*11 #누적 합을 저장하기 위한 변수
s, e = 0 #100보다 작은 수, 큰 수를 비교하기 위한 변수

for i in range(10):
    prefix_sum[i+1] = prefix_sum[i] + n[i] #누적 합
    
    if prefix_sum[i+1] >= 100: #100보다 크거나 같아지면 100이하/이상값을 저장하고 반복문 중단
        s = prefix_sum[i]
        e = prefix_sum[i+1]
        break
    else: #누적 합이 100이상이 안 될 경우를 대비해 값을 매번 갱신
        s = prefix_sum[i]
        e = prefix_sum[i+1]

#100이하, 100이상의 값을 비교해서 출력한다.
if 100 - s == e - 100: 
    print(e)
elif 100 - s <= e - 100:
    print(s)
else:
    print(e)

Another Solution

ans,score = 0,0
for i in range(10):
    score+=int(input()) #입력과 동시에 누적 합을 구한다.
    if 100-ans >= abs(100-score): #100과 가까운 두 수를 비교한다. 
        ans = score
print(ans)