논리식의 일부를 바꿔서 원하는 결과가 나오게 만드는 방법

31835번: 수식 고치기 (acmicpc.net)

 

T,F,&,|으로만 이루어진 논리식에서 일부를 바꿔서 원하는 결과가 나오게 만들고 싶다.

 

연산은 왼쪽에서 오른쪽으로 차례대로 진행하고, 논리식을 최소로 바꿀때, 최소횟수를 구한다면

 

예를 들어 F & F가 주어질때 연산 결과를 T로 만들고 싶다면 T & T로 바꾸면 되니 2번이다.

 

단순하게 생각한다면 가능한 경우 다 조사해서 다 바꿔볼려고  할텐데.. 

 

그러자니 어떻게 바꿔야할지도 모르겠고 길이가 N <= 1999니까.. 다 바꿔볼려면 2**1999가지인데..

 

하다가 머리를 굴려보니..

 

&와 |으로 이루어진 연산을 생각해보면

 

T & T = T

 

T & F = F

 

F & T = F

 

F & F = F

 

T | T = T

 

T | F = T

 

F | T = T

 

F | F = F

 

이렇게 되니까 a1 b1 a2 b2 a3 b3 .... an-1 bn-1 an으로 이루어진 식이 있을때

 

a1 ~ an-1까지를 계산해서 an+1 bn-1 an 이라는 논리식을 만들고 bn-1과 an만 원하는 결과가 나오도록 바꾸면 되는거 아닐까?

 

그러니까 T & F | F | T & F라는 식이 T가 나오게 바꾸고 싶다면

 

T & F | F | T까지 먼저 계산하면 T니까 T & F = T가 나오게 하면 된다

 

그러기 위해서 바꿀 수 있는건 & 와 F인데 최소 횟수로 바꾸고 싶다면 &를 |으로 바꾸면 1번만에 T로 만들 수 있다

 

따라서 길이가 1인 식이 주어지면 그냥 바로 원하는 결과와 비교해서 서로 다르면 바꾸는 횟수는 1번, 같으면 바꾸는 횟수는 0번

 

길이가 3 이상인 식이 주어지면, 마지막 2개를 제외한 나머지를 앞에서부터 차례로 보면서 계산하고

 

계산 결과 (연산) (값) 상태로 둔 다음 원하는 결과가 나오는 최소의 경우를 잘 생각해서 각 경우에 따라 해주면 될 것 같다

 

예를 들어 T & F = T가 되도록 하고 싶다면.. F를 T로 바꾸거나 &를 |으로 바꾸면 되니 1번이고

 

T | F = T가 되도록 하고 싶다면? 안바꿔도 되니까 0번이고

 

F | T = F가 되도록 하고 싶다면? T를 F로 바꾸거나 |를 &로 바꾸거나 1번

 

T & T = F가 되도록 하고 싶다면? T를 F로 바꾸고 &도 |으로 바꿔야하니 2번

 

.... 이런식으로 (연산자)와 (값)의 종류에 따라 경우를 나눠서.. 하면 될듯

 

#주어진 논리식의 일부를 적당히 바꿔서 원하는 결과가 나오도록 하는 최소 횟수
#왼쪽부터 마지막 2개를 제외한 논리 연산을 수행해서 a (연산자) (b)의 형태로 두고
#(연산자)와 (b)만 적당히 바꾸면 반드시 원하는 결과가 나오게 할 수 있다
n = int(input())

s = list(input().split())

f = input()

v = s[0]

#연산식 길이가 1인 경우
#연산식과 그대로 비교해서 같으면 안바꾸면 되고 다르면 바꾸면 되고
if n == 1:
    
    if v == f:
        
        print(0)
    
    else:
        
        print(1)

#길이가 3 이상인 경우
#마지막 2개를 제외한 나머지를 왼쪽부터 차례로 연산
else:

    for i in range(2,n-2,2):
        
        if s[i-1] == '&':
            
            if v == 'T' and s[i] == 'T':
                
                v = 'T'
            
            else:
                
                v = 'F'
        
        else:
            
            if v == 'F' and s[i] == 'F':
                
                v = 'F'
            
            else:
                
                v = 'T'
    
    #v s[n-2] s[n-1] 형태의 식에서 원하는 결과 f가 되도록 만들려면?
    #연산자 s[n-2]와 s[n-1]에 따라 최소 횟수를 잘 생각해서.. 모든 경우를 다 계산
    if s[n-2] == '&':
        
        if v == 'T' and s[n-1] == 'T':
            
            if f == 'T': #T & T = T인 경우
                
                print(0)
            
            else: #T & T = F인 경우 T만 F로 바꾸면 
                
                print(1)
        
        else: #F & F, F & T, T & F인 경우
            
            if f == 'F': #결과가 F면 안바꿔도 되고
                
                print(0)
            
            else:
                
                #F & F = T인 경우는 &를 |으로 F를 T로 바꿔야만 가능
                if v == 'F' and s[n-1] == 'F':
                    
                    print(2)
                
                #F & T = T, T & F = T인 경우 &를 |으로 바꾸면 가능
                else:
                    
                    print(1)
    
    else:
        
        #F | F인 경우
        if v == 'F' and s[n-1] == 'F':
            
            if f == 'F': #F | F = F인 경우
                
                print(0)
            
            else: # F | F = T인 경우, F를 T로 바꾸면 가능
                
                print(1)
        
        #T | F, T | T, F | T인 경우
        else:
            
            if f == 'T': #안바꿔도 가능
                
                print(0)
            
            else:
                
                #T | T = F인 경우 T를 F로 바꾸고 |를 &로 바꿔야
                if v == 'T' and s[n-1] == 'T':
                    
                    print(2)
                
                #T | F = F, F | T = F인 경우, |를 &로 바꾸면 가능
                else:
                    
                    print(1)