[BOJ: 2851] - Python / 파이썬 - 슈퍼마리오

문제

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

시간 복잡도

• 최대 n만큼의 반복문을 탐색하기 때문에, $O(n)$.
• n의 최대 값은 10이기 때문에, 제한시간 조건에 충분히 부합한다.

문제 접근법

1. 10개의 버섯을 차례대로 탐색한다.
2. 탐색하면서 현재 버섯의 점수를 계속 더한다.
3. 점수가 100일 경우, 즉시 반복문을 종료한다.
4. 점수가 100보다 큰 경우, 처음부터 현재 점수까지 더한 값과 이전 점수까지만 더한 값을 비교한다.
   4-1. 현재 점수까지 더한 값이 이전 점수까지만 더한 값보다 100과의 차이가 큰 경우, 이전 점수까지만 더한 값을 반환하고 출력한다.

코드

# BOJ
# B1 - 2851(슈퍼마리오)

def getABS(n):
    return abs(100 - n)

def solution(mushrooms) -> int:
    ans = 0

    for mushroom in mushrooms:
        ans += mushroom

        if ans == 100:
            break
        if ans > 100 and getABS(ans) > getABS(ans - mushroom):
            ans -= mushroom
            break
    
    return ans

mushrooms = [int(input()) for _ in range(10)]
result = solution(mushrooms)

print(result)