백준 2851 파이썬

문제 링크

https://www.acmicpc.net/problem/2851

2851번: 슈퍼 마리오

 

시간 제한 / 메모리 제한

1 초

128 MB

 

문제

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

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

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

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

입력

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

출력

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

예제 입력

1
2
3
5
8
13
21
34
55
89

예제 출력

87

 

풀이 코드

lst = [int(input()) for _ in range(10)]
res = 0

for i in range(len(lst)):
    res += lst[i]
    if res == 100:
        print(100)
        exit()
    if res > 100:
        cur = res
        prev = res - lst[i]
        if abs(100 - cur) < abs(100 - prev):
            print(cur)
            exit()
        elif abs(100 - cur) == abs(100 - prev):
            print(cur)
            exit()
        else:
            print(prev)
            exit()

print(res)

 

1. 처음 버섯부터 차례대로 먹으면서 점수가 100이 되는 순간 혹은 100이 넘는 순간을 찾는다.
2. 점수가 정확히 100이면, 100을 출력한다.
3. 점수가 100이 넘으면, 현재 버섯을 먹은 점수와 이전 버섯까지만 먹은 점수 중 100과 더 가까운 점수를 출력한다.
4. 만약 두 점수가 100까지의 절댓값이 같으면 둘 중 더 큰 점수를 출력한다.
5. 만약 버섯을 다 먹었는데 100이 안 넘으면 총 합계를 출력한다.

 

언제 어떻게 버섯 먹기를 멈추어야 하나 고민이 필요한 문제였다.

 

어찌 됐든 이전 값 혹은 다음 값과 비교해 어떤 값이 100에 가까운지 비교해야 할 필요가 있었는데, 이 뜻은 100을 기준으로 앞 뒤 점수를 고려하면 된다는 뜻이다.

 

즉 현재 버섯을 먹고 100이 넘었다는 것은, 직전 버섯까지는 100이 안 넘었다는 뜻이고, 이때 현재 버섯을 먹은 점수와 이전 버섯까지만 먹은 점수 중 100까지의 절댓값이 더 작은 점수를 출력하면 된다.