[Python/BOJ] 백준 23325 마법천자문_DP

 

상황을 잘 나눠서 상황에 따라 잘 계산해줘야한다. 

dy[j]의 의미는 j번째 문자열까지 연산했을 때 연산의 최댓값이다. 

 

 

코드 : 

 

if __name__=="__main__" :
    a = list(input())
    dy= [-int(1e9)]*(len(a))
    # dy[j] : j가 마지막 숫자일 때의 최대 계산 결과 
    
    # 글자가 한글자라면 숫자로 해석 
    if len(a) ==1 :
        if a[0] == '+' : print(10)
        else : print(1)
    # 글자가 여러 글자라면 
    else :
        # 첫 글자 - 은 연산자가 아님 
        if a[0] == '-' : dy[0] = 1 
        else : 
            dy[0] = 10
            # 이왕이면 큰 숫자를 얻는게 좋음
            if a[1] == '-' : dy[1] = 11 
        
        # 나머지 숫자들을 돌면서 
        for i in range(2,len(a)) :
            # 10 
            if a[i] == '+' : 
                if a[i-1] =='-' :
                    dy[i] = dy[i-2] -10
                else :
                    dy[i] = dy[i-2] + 10
            
            else :
                if a[i-1] =='-' :
                    # 1 
                    dy[i] =dy[i-2]-1
                # + - , 11 을 의미하거나 1을 더하거나 
                else :
                	# 11을 의미하려면 3번째 이상이여야함 
                    # 3번째 이상  -> 11 을 의미 
                    if i>=3 :
                        # - + - 
                        if a[i-2] =='-' :
                            dy[i] = max(dy[i-2]+1, dy[i-3]-11) 
                        # + + -
                        else :
                            dy[i] = max(dy[i-2]+1, dy[i-3]+11)
                    # 3번째 이상이 아니다. 
                    # -> 1을 더함 
                    else :
                        # + - 
                        dy[i] = dy[i-2] +1 
        print(dy[-1])

 

 

 

만약 1글자라면 

+ 면 10 , -면 1을 출력하고 끝낸다.

 

1글자 이상이라면

첫글자가 + 면 dy[0]에 10을 저장하고

첫글자 + 두번째 글자 - 라면 dy[1] = 11을 한다. 

첫글자가 - 면 dy[0]  = 1을 한다. 

 

 

세번째 글자부터 돌리기 시작한다. 

코드 별로 확인하려면 주석 확인!! 

 

 

+ 라면 10인 경우가 있다. 10을 더하거나 빼거나

 

 

- 라면 앞에 뭐가 있는지 확인한다. 

앞에 -가 있다면 1을 빼준다.

앞에 + 가 있다면 11일수도 있고 1을 더한다는 것일 수 있다.

3번째 이상인지 확인해서 3번째 이상이라면 11을 더하거나 빼거나 하는 값과 1을 더하는 값 중 최댓값을 저장한다. 

만약 3번째 이상이 아니라면 11일 수 가 없다. 그냥 1을 더해준다.