[ BOJ ] 20047 : 동전 옮기기 ( GOLD 2 ) / Python

>> 문제 바로가기 (https://www.acmicpc.net/problem/20047)

문제

100 원짜리 동전과 10 원짜리 동전이 임의의 순서로 한 선 위에 나열되어 있다고 하자. 이제 여기서 ‘두 손가락 이동’ 을 아래와 같이 정의하자.

• 단계 1: 임의의 두 동전을 선택한다.
• 단계 2: 단계 1 에서 선택한 두 동전을 둘의 순서를 유지한 채 임의의 위치로 이동한다. (두 동전 모두 제자리에 있거나 두 동전의 순서를 유지한다면 하나만 이동해도 된다.)

‘두 손가락 이동’ 후에도 다른 동전들 간의 순서는 그대로 유지된다. 예를 들어 100 원을 o, 10 원을 x 라 했을 때, 초기에 동전이 oxoxoxxxoo 와 같이 나열되어 있다 하자. 이제 이들 중 굵게 표시된 두 동전을 선택하여 두 손가락 이동을 한번 한 경우, 나올 수 있는 여러 결과들 중에서 네 가지 결과만 아래에 표시했다 (아래 예시에 없는 다른 결과들 또한 나올 수 있음에 유의하자).

• oxoxoxxxoo
• oxooxxxxoo
• oxoxoxxoxo
• oxoxoxxxoo

n 개의 동전이 나열되어 있는 두 상태 S, T와 함께 두 손가락 이동을 위해 선택할 두 동전의 위치가 주어졌을 때, 한번의 두 손가락 이동을 통해 S에서 T로의 변환이 가능한지 결정하는 프로그램을 작성하시오.

입력

입력은 표준입력을 사용한다. 첫 번째 줄에 나열된 동전 개수를 나타낸 양의 정수 n (3 ≤ n ≤ 10,000)이 주어진다. 다음 두 줄에 n 개의 동전이 나열된 상태인 S 와 T 가 각각 주어지며, 이 때 S와 T 는 o 와 x 로 이루어진 길이가 n 인 문자열로 표현된다 (o 와 x 는 모두 소문자이다). 동전의 위치는 왼쪽에서 오른쪽으로 0부터 n − 1까지 차례대로 번호를 매겨 구분한다. 마지막 줄에는 두 손가락 이동을 위해 선택할 두 동전의 위치 i와 j가 주어지며, i는 j 보다 작다 (0 ≤ i < j ≤ n − 1).

출력

출력은 표준출력을 사용한다. 한번의 두 손가락 이동을 통해 S 에서 T로의 변환이 가능한 경우 YES 를, 그렇지 않은 경우 NO 을 출력한다.

풀이 과정

DP 식을 세워 문제를 풀이했다. 편리한 계산을 위해 S에서 i 번째 동전과 j 번째 동전을 제거하고 시작했다.

 

dp[i][j] = i 번째 문자를 추가했을 때, j 번 인덱스까지 공통된 문자의 개수

• i = 0 : 아무 문자도 추가하지 않았을 때 S와 T의 공통된 문자 개수를 센다.
• i = 1 : 첫 번째 동전 문자를 추가했을 때 S와 T의 공통된 문자 개수를 센다. j - 1 번째 인덱스까지 아무 문자도 추가하지 않았을 때 (i = 0) 공통된 문자 개수가 0보다 크다면 첫 번째 동전 문자를 추가해 공통된 문자 개수를 1 늘렸다. 혹은 S의 맨 첫 번째에 첫 번째 동전 문자를 추가할 수 있다.
  
  첫 번째 동전 문자를 j - 1 번 인덱스까지 이미 추가한 상태에서 S[j-1] 과 T[j] 가 같다면, 계속해서 공통된 문자 개수 상태를 이어나가도록 dp[i][j-1] 도 고려한다. ( 이미 첫 번째 동전 문자를 추가했다면, S가 첫 번째 동전 문자가 추가된 부분부터 한 칸 밀려 S[j-1] 과 T[j] 가 같은 위치가 되기 때문이다. )
• i = 2 : 두 번째 동전 문자를 추가했을 때 S와 T의 공통된 문자 개수를 센다. j - 1 번째 인덱스까지 첫 번째 동전 문자를 추가한 상태일 때 (i = 1) 공통된 문자 개수가 0보다 크다면 두 번째 동전 문자를 추가해 공통된 문자 개수를 1 늘렸다.
  
  두 번째 동전 문자를 j - 1 번 인덱스까지 이미 추가한 상태에서 S[j-2] 와 T[j] 가 같다면, 계속해서 공통된 문자 개수 상태를 이어나가도록 dp[i][j-1] 도 고려한다. ( 이미 두 번째 동전 문자를 추가했다면, S가 첫 번째 동전 문자가 추가된 부분부터 한 칸, 두 번째 동전 문자가 추가된 부분부터 한 칸 밀려 S[j-2] 과 T[j] 가 같은 위치가 되기 때문이다. )

import sys
input = sys.stdin.readline

n = int(input().rstrip())
s = list(input().rstrip())
t = list(input().rstrip())
i, j = map(int, input().rstrip().split())

need_two = [s[i], s[j]]
del s[j]
del s[i]

dp = [[0 for _ in range(n)] for _ in range(3)]
# dp[i][j] : 문자 i 개 추가했을 때 j 번째 인덱스까지 같은 문자 개수

for j in range(n):
    for i in range(3):
        if i == 0:
            if len(s) > j and s[j] == t[j]:
                if j > 0: dp[i][j] = dp[i][j-1] + 1
                else: dp[i][j] = 1
        elif i == 1:
            if j > 0 and need_two[0] == t[j] and dp[i-1][j-1] > 0:
                dp[i][j] = dp[i-1][j-1] + 1
            elif need_two[0] == t[j]: dp[i][j] = 1
            if j - 1 >= 0 and len(s) > j - 1 and s[j-1] == t[j] and dp[i][j-1] > 0:
                dp[i][j] = max(dp[i][j], dp[i][j-1] + 1)
        else:
            if j > 0 and need_two[1] == t[j] and dp[i-1][j-1] > 0:
                dp[i][j] = dp[i-1][j-1] + 1
            if j - 2 >= 0 and len(s) > j - 2 and s[j-2] == t[j] and dp[i][j-1] > 0:
                dp[i][j] = max(dp[i][j], dp[i][j-1] + 1)


if dp[2][n-1] == n: print('YES')
else: print('NO')