[Python] 23325번 마법천자문

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

23325번: 마법천자문

---

 

24/02/08

 

 

업 다운 랜디를 하다 만난 문제로, 처음에 어떤 알고리즘을 적용해야 할 지 몰라 많이 헤맸던 문제다.

---

 

문제 접근 방식:

 

 

처음에 접근했던 방식은 무지성 dfs였다.

 

열심히 짰지만 당연히 시간초과가 났다.

 

태그를 까고 곧바로 어떻게 풀지 알아버렸는데, 태그는 DP였다.

 

상태 식은 다음과 같이 정의된다.

 

$$DP[i] = i\textrm{번째 문자까지 보았을 때 해석할 수 있는 가장 큰 계산 결과}$$

 

그렇다면, 현재 문자와 그 이전문자, 그 이전이전 문자가 무엇이냐에 따라서 다음과 같은 4가지의 결과 중에 나올 수 있을 것이다.

 

즉, 다음과 같은 점화 식이 성립될 것이다.

 

$$DP[N] = DP[N-2] + line[N]$$

$$= DP[N-2] - line[N]$$

$$= DP[N-3] + 11$$

$$= DP[N-3] - 11$$

 

이때, $line[N]$은 현재 문자가 $+$라면 $10$을, $-$라면 $1$을 나타내는 숫자다.

 

만약 이전 문자가 $-$라면, 두 번째 점화식이 나올 수 있을 것이다.

 

만약 이전 문자가 $+$라면, 첫 번째 점화식이 나올 수 있을 것이다.

 

만약 이전 이전 문자가 $+$이고, 이전 문자와 현재 문자를 합쳐서 해석한 결과가 $11$이라면 세 번째 점화식이 나올 수 있을 것이다.

 

마찬가지로, 이전 이전 문자가 $-$이고 이전 문자와 현재 문자를 합친 결과가 $11$이라면 네 번째 점화식이 나올 수 있을 것이다.

 

총 $4$가지의 경우가 생기는데, 이 $4$가지의 경우 중 최댓값이 문제에서 요구하고자 하는 값이 될 것이다.

 

만약 4가지 경우가 모두 성립하지 않는다면, 그때는 해석할 수 없는 것이므로 None으로 처리했다.

 

이 None을 처리하는데 조금 애를 먹어서 실수로 많이 틀렸다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 23325번 마법천자문
# 백트래킹, 브루트 포스
import sys
input = sys.stdin.readline
sys.setrecursionlimit(500_000)
MAX = 1_000_000_000
line = input().rstrip()
N = len(line)
max_val = -MAX
def backtrack(line, index, total_val):
    global max_val
    if index == N:
        if total_val > max_val:
            max_val = total_val
        return
    if index+1 >= N: return
    if line[index] == '-':
        if index+2 < N:
            if line[index+1] + line[index+2] == '+-':
                backtrack(line, index+3, total_val - 11)
        if line[index+1] == '+':
            backtrack(line, index+2, total_val - 10)
        if line[index+1] == '-':
            backtrack(line, index+2, total_val - 1)
    else:
        if index+2 < N:
            if line[index+1] + line[index+2] == '+-':
                backtrack(line, index+3, total_val + 11)
        if line[index+1] == '+':
            backtrack(line, index+2, total_val + 10)
        if line[index+1] == '-':
            backtrack(line, index+2, total_val + 1)
    return

if line[0] == '+':
    if N >= 2 and line[1] == '-':
        backtrack(line, 2, 11)
    backtrack(line, 1, 10)
else:
    backtrack(line, 1, 1)

print(max_val)

# 23325번 마법천자문
# DP
'''
접근 방법:
DP[i] = i번째 문자열까지 보았을 때 해석할 수 있는 가장 큰 계산 결과
DP[N] = DP[N-2] + line[N] or
      = DP[N-2] - line[N] or
      = DP[N-3] + line[N] or
      = DP[N-3] - line[N]
반드시 하나 이상의 올바른 해석이 존재하는 입력만 주어진다고 했다.
'''
import sys
input = sys.stdin.readline

def main():
    line = input().rstrip()
    N = len(line)
    DP = [None for _ in range(N)]
    if N == 1:
        if line[0] == '+':
            print(10)
        else:
            print(1)
        return
    if N == 2:
        print(11)
        return
    if line[0] == '+':
        DP[0] = 10
        if line[1] == '-':
            DP[1] = 11
    else:
        DP[0] = 1
    for i in range(2, N):
        possibles = []
        if DP[i-2] != None:
            if line[i-1] == '+':
                if line[i] == '+':
                    possibles.append(DP[i-2] + 10)
                else:
                    possibles.append(DP[i-2] + 1)
            else:
                if line[i] == '+':
                    possibles.append(DP[i-2] - 10)
                else:
                    possibles.append(DP[i-2] - 1) 
        if DP[i-3] != None:
            if line[i-1]+line[i] == '+-':
                if line[i-2] == '+':
                    possibles.append(DP[i-3] + 11)
                else:
                    possibles.append(DP[i-3] - 11)
        if possibles != []:
            DP[i] = max(possibles)
    print(DP[N-1])
    return

main()