문자를 하나만 바꾸거나, 처음부터 연속된 k개를 바꿔서 전부 같은 문자로 바꾸는 다이나믹 프로그래밍

2806번: DNA 발견

 

A나 B로 이루어진 문자열에서 첫번째 연산은 하나의 문자를 A는 B로, B는 A로 바꾸는 것이다.

 

두번째 연산은 처음부터 연속된 K(1 <= K <= N)개의 문자를 선택하여 전부 A는 B로 B는 A로 뒤집는 것이다.

 

예를 들어 ABBA라면, B 2개를 각각 A로 바꾸면 AAAA가 되고

 

처음부터 3개의 문자 ABB를 뒤집어서 BAA로 바꾸고, BAAA에서 첫번째 문자 B를 A로 바꾸면 2회만에 AAAA로 된다.

 

이러한 두 연산으로 모든 문자를 A로 바꾸고 싶다

 

가능한 최소 연산 횟수는?

 

------------------------------------------------------------------------------------------------------------------------------------------------------------

 

처음부터 굉장히 어렵다...

 

처음부터 i개의 문자를 모두 A로 바꾸는데 필요한 최소 연산 횟수를 dp1[i]

 

처음부터 i개의 문자를 모두 B로 바꾸는데 필요한 최소 연산 횟수를 dp2[i]

 

만약 i번째 문자가 A라면, 

 

이미 A이므로, A로 바꿀 필요가 없기 때문에 i-1번째까지 A로 바꾼 횟수 dp1[i-1]과 같다 dp1[i] = dp1[i-1]

 

만약 i번째 문자가 B라면,

 

i-1번째까지 A로 바꾼 횟수에 i번째 문자만 A로 바꿔서 dp1[i] = dp1[i-1] + 1

 

혹은 i-1번째 문자까지 B로 바꿔서 dp2[i-1]회

 

그리고 처음부터 연속된 k = i번째 문자까지 한번에 뒤집는 2번째 연산을 적용하면 1회 더해져서

 

dp2[i-1] + 1회

 

즉, dp1[i] = min(dp1[i-1] + 1, dp2[i-1] + 1)

 

그러면 dp2[i]는 어떻게 구해?

 

비슷하게 i번째 문자가 B라면, 바꿀 필요가 없으므로 dp2[i] = dp2[i-1]

 

i번째 문자가 A라면, i-1번째까지 B로 바꾼거에 i번째 문자만 B로 바꾸든지, dp2[i] = dp2[i-1] + 1

 

혹은 i-1번째 문자까지 A로 바꿔서 dp1[i-1] + 처음부터 연속된 i번째 문자까지를 B로 뒤집는 두번째 연산 적용 1회

 

 = dp1[i-1] + 1

 

즉, dp2[i] = min(dp2[i-1] + 1, dp1[i-1] + 1)

 

당연히 처음 문자가 A이면 dp1[0] = 0, dp2[0] = 1, B이면 dp1[0] = 1, dp2[0] = 0으로 초기화하겠지

 

n = int(input())

s = input()

INF = 10**18

dp1 = [INF]*n
dp2 = [INF]*n

if s[0] == 'A':

    dp1[0] = 0
    dp2[0] = 1

else:
    
    dp1[0] = 1
    dp2[0] = 0

for i in range(1,n):
    
    if s[i] == 'A':
        
        dp1[i] = dp1[i-1]
        dp2[i] = min(dp2[i],dp2[i-1] + 1,dp1[i-1]+1)

    else:
        
        dp1[i] = min(dp1[i],dp1[i-1] + 1,dp2[i-1]+1)
        dp2[i] = dp2[i-1]

print(dp1[n-1])

 

 

이 두 dp를 잡는게 굉장히 어렵다...

 

처음부터 i개의 문자를 모두 A로 바꾸는데 필요한 최소 연산 횟수를 dp1[i]

 

처음부터 i개의 문자를 모두 B로 바꾸는데 필요한 최소 연산 횟수를 dp2[i]

 

----------------------------------------------------------------------

 

처음부터 k개의 문자를 지정해서 바꾸거나, 특정 한 문자를 바꾸기 때문에

 

뒤에서부터 순회한다면 그리디하게 해결해볼 수도 있다.

 

뒤에서부터 순회해서 현재 보는 문자가 A라면, 바꿀 필요가 없기 때문에 넘어간다.

 

그러나 현재 보는 문자가 B라면 그 앞의 문자가 A라면, 즉 .....ABAAA로 되어있다면

 

그냥 현재 문자를 바꾸는 첫번째 연산을 적용하면 된다

 

반면 그 앞의 문자가 B라면, .....BBAAAA로 되어있다면

 

앞에서부터 i번째 문자까지 뒤집는 두번째 연산을 적용하면 된다

 

왜냐하면.. 귀납법으로 증명 가능하다.

 

길이가 2이면 BB인 경우 뒤집으면 1번에 가능하고, AB인 경우 그냥 B를 바꾸면 되니까 성립한다.

 

길이가 n-1일때 위 해법이 성립한다고 해보자.

 

길이가 n인 경우 n번째 문자가 A라면 n-1번째 문자를 뒤집는 문제로 바뀐다. 따라서 위 해법을 쓰면 된다.

 

n번째 문자가 B라면, n-1번째 문자가 A인 경우 n-1번째 문자까지는 위 해법이 성립하기 때문에 n-1번째 문자는 뒤집지 않아야한다.

 

따라서, n번째 문자 B만 뒤집어야한다.

 

반대로 n-1번째 문자가 B인 경우 n-1번째 문자까지는 위 해법이 성립하므로 n-1번째 문자도 바꿔야한다.

 

그래서 n-1번, n번을 모두 뒤집는 연산을 적용하는게 맞다.

 

따라서 길이가 n일때도 위 해법이 참이다.

 

n = int(input())

s = list(input())

count = 0

r = False

for i in range(n-1,0,-1):
    
    if r == False:

        if s[i] == 'B':

            if s[i-1] == 'A':

                count += 1

            else:

                r = True
                count += 1
    
    else:
        
        if s[i] == 'A':
            
            if s[i-1] == 'B':
                
                count += 1
            
            else:
                
                r = False
                count += 1

if r:
    
    if s[0] == 'A':
        
        count += 1

else:
    
    if s[0] == 'B':
        
        count += 1
        
print(count)

 

 

여기서 핵심은 r을 flag로 세워서 모든 문자를 일일이 뒤집지 않는 것이다

 

s[i] = B이고 s[i-1]도 B인 경우 r = True로 세워서 뒤집어졌다는 표시를 하고,

 

뒤집어 진 경우라면 모든 것을 반대로 하면 된다

 

s[i] = B면 넘어가고

 

s[i] = A인 경우 s[i-1] = A이면 뒤집고 r = False로 다시 바꿔주고

 

s[i-1] = B인 경우 뒤집지 말고 카운팅하고