[BOJ][🟡4][백준#17255] N으로 만들기

문제 출처

BAEKJOON Online Judge #17255

문제

준하는 노트에 수를 적다가 수가 만들어지는 방식을 깨달았다. 처음에 어떤 숫자 하나를 적고 만들어진 수의 왼쪽이나 오른쪽에 숫자를 계속 붙이면 어떤 수 N이든 만들 수 있다는 것이다. 다시 말해 어떤 수 N을 만들기 위해서는, 처음에 어떤 숫자를 하나 적고 아래의 두 가지 행동을 반복한다.

수의 왼쪽에 숫자를 하나 적는다. 수의 오른쪽에 숫자를 하나 적는다.

준하는 어떤 수 N을 만드는 방법의 수가 몇 가지인지 궁금해졌다. 이를 알아내는 프로그램을 작성해주자. 숫자를 적는 과정에서 나온 수가 순서대로 모두 같다면 같은 방법이다. 단, 숫자를 적는 과정에서 수는 0으로 시작할 수 있다.

입력

음이 아닌 정수 N이 주어진다. (0 ≤ N ≤ 10,000,000)

출력

N을 만드는 방법의 수를 출력한다.

예제

예제 1

입력

521

출력

4

예제 2

입력

9111

출력

4

My Sol

def main():
    def dfs(S, l):
        if l == 1: return 1
        if D.get(S, 0): return D[S]

        left_S, right_S = S[1:], S[:-1]
        D[S] = dfs(left_S, l-1)
        if left_S == right_S: return D[S]
        D[S] += dfs(right_S, l-1)
        return D[S]

    S = input()
    l = len(S)
    if l==1: return 1
    D = {}
    dfs(S, l)
    return D[S]

print(main())

DP 방식을 일부 차용해 문제를 해결했다. 타일 맞추기처럼 앞뒤로 숫자들을 추가한다고 생각해보는 것이다. 그렇다면 최초 받은 수를 만들기 위해서는 이보다 길이가 1 작은 수로부터 뒤에 숫자 하나를 붙이거나, 앞에 숫자 하나를 붙이는 것이다. 이때 수를 깎아내리다가 특정 수에 다다르면, 이전에 나왔던 수일 수 있다. 그렇다면 그 수로부터 깎아내리는 경우의 수는 다시 해보지 않아도 되므로 memoization한다. 다만 배열에 저장하는 것은 아니고, dictionary에 저장했다.

해당 수까지 다다르는 경로는 유니크하다는 전제인데, 좌측과 우측을 각각 추가하는 경우를 모두 더하기 위해서는 좌측의 하나, 우측의 하나를 뺀 수가 서로 달라야 한다. 다시 말하면 좌측과 우측의 수를 뺀 것이 같다면, 경로가 같으므로 다른 경우가 아닌 것이다. 때문에 하나를 뺀 경우만 고려하면 되겠다.

숫자가 한 자리라면 더 빼고 붙일 것이 없으므로 경우의 수 1을 return하고, 만약 dictionary D에 있는 수라면 해당 수가 깎아지는 경우의 수를 기록한 D[S]를 반환한다. 만약 첫 수가 10을 넘지 않는다면, 그냥 1을 반환한다.

결과

맞았습니다!!