문제

공백 없이 숫자가 연속되어 쓰여 있다.

당신은 이 숫자를 적절히 끊어서 N개의 1자리 혹은 2자리 수로 나누어야 한다.

어떻게 나누어야 N개의 수의 합이 가장 커질까?

입력

하나의 수로 보았을 때 200,000,000 이하인 수열이 주어진다.

입력 예시

138947192

출력

수열을 일의 자리 혹은 십의 자리 수로 끊어 얻은 수들의 최대 합을 출력한다.

출력 예시

296

문제 풀이

• DP 를 이용해서 푸는 방식을 택했다.
• 평소 Dyamic Programming에 대해서 이해를 잘 못하고 있어서 여러가지 데이터를 좀 검색해가면서 진행함.
• 일단 해당 문제를 진행하기 전 이해를 위해 직접 그려가면서 진행했다.

(그림이 조금 그렇기는 한데) 1234로 예시를 들고 하나씩 나눠서 케이스를 나눠봤을때 가장 큰값끼리 더해주는 방식으로 진행하였다.

• 진행하면서 조금 헷갈렸던 것은 list를 나누다보니 자꾸 int 가 아니라는 등, 출력 관련해서 애를 좀 먹었는데 그 부분은 아예 합쳐서 변환을 해주는 방식으로 진행했다. -> int(''.join(numbers[i - 2:i])))
• 이런 비슷한 문제를 여러번 풀어야 이해가 될 것 같다.

def find_max_sum(numbers):
    n = len(numbers)
    dp = [0] * (n + 1)

    dp[1] = int(numbers[0])
    
    # 1의 자리로 나누는 경우와 2의자리로 나누는 경우의 max값을 찾아가도록 구현
    for i in range(2, n + 1):
        dp[i] = max(dp[i - 1] + int(numbers[i - 1]), dp[i - 2] + int(''.join(numbers[i - 2:i]))) # 변환 시 오류가 나서 합쳐서 변환하는 것으로 변경

    return dp[n]

# 입력 예시
numbers = list(input())

result = find_max_sum(numbers)
print(result)