목적

AtCoder 버전! 개미모토(초급편)에서 「많은 수식」으로 망설였으므로 이해한 것을 비망록으로 남긴다.

문제

1 이상 9 이하의 숫자만으로 구성된 문자열 S가 주어집니다. 이 문자열 내에서이 문자와 문자 사이에 여러 위치에 +를 넣을 수 있습니다. 하나도 넣지 않아도 괜찮습니다. 그러나 +는 연속해서는 안됩니다.

이 방법으로 가능한 모든 문자열을 수식으로 간주하고 합계를 계산할 수 있습니다.

가능한 모든 수식의 값을 계산하고 그 합계를 출력하십시오.

s = input()
n = len(s)

def dfs(i, f):
    if i == (n - 1):
        return sum(list(map(int, f.split("+"))))
    return dfs(i + 1, f + s[i + 1]) + dfs(i + 1, f + "+" + s[i + 1])

print(dfs(0, s[0]))

구현 내용

dfs(0, s[0]) 를 호출했을 때의 모습을 보여줍니다. s = "125"이므로 그림에서는 s[0]을 문자열의 "1"로 나타냅니다. 마찬가지로 s[1]을 문자열의 "2"로, s[2]를 문자열의 "5"로 나타냅니다. 재귀 적으로 dfs를 호출하여 합계를 얻고 있음을 알 수 있습니다.

참조