문제 정보
- 문제 번호 : 2181M
- 문제 이름 : Medical Parity
- 문제 링크 : https://codeforces.com/problemset/problem/2181/M
- 정답 코드 : https://github.com/dalmengs/algorithm-solutions/blob/main/codeforce-2181-m/main.py
- 난이도 : 1700
- 체감 난이도 : Gold 1
- 알고리즘 : DP
문제 설명
0과 1로 이루어진 두 개의 이진 문자열 x, y가 주어진다.y[i]는 (1번째 글자부터 i번째 글자까지의 문자열 x 내 1의 개수) % 2 를 의미한다.
예를 들어, 문자열 x = 11101, y = 10110에서,
y[1]은x[1:2] = "1"에서 1이 한 개이므로,y[i] = 1 % 2 = 1이 된다.y[2]은x[1:3] = "11"에서 1이 두 개이므로,y[i] = 2 % 2 = 0이 된다.y[3]은x[1:4] = "111"에서 1이 세 개이므로,y[i] = 3 % 2 = 1이 된다.y[4]은x[1:5] = "1110"에서 1이 세 개이므로,y[i] = 3 % 2 = 1이 된다.y[5]는x[1:6] = "11101"에서 1이 네 개이므로,y[i] = 4 % 2 = 0이 된다.
하지만 비트가 뒤바뀐 채로 넘어오는 경우도 있다.
위 예시에서 x는 바뀌지 않았고, y의 세 번째 비트만 뒤바뀐 예시로, x' = 11101, y' = 10010 가 x, y의 뒤바뀐 문자열 중 하나이다.
이 문제의 목표는 뒤바뀐 문자열 x', y'이 주어질 때, 이 문자열의 비트를 자유롭게 뒤바꿔서 올바른 x, y를 얻어내기 위해 최소 몇 번 비트를 바꿔야 하는지 구하는 것이다.
x' = 11101
y' = 10010
x = 11101
y = 10110위와 같은 경우, 세 번째 비트가 잘못되었고, 이 비트만 바꾸면 올바른 x, y 문자열이 된다.
[원문]
문제 해결
보자마자 [BOJ 1006] 습격자 초라기 이 문제가 생각이 났다.
위 아래로 두 개의 상태를 관리해야 하고, 이전 상태를 단순히 2차원 배열이 아닌, 조금 더 디테일하게 저장해야 하기 때문이다.
그래도 이 문제는 위 문제보다는 쉬워서 DP 점화식 세우는 것이 더 수월했다.
나는 DP 배열을 dp[i][a][b]로 세웠는데, 의미는 아래와 같다. (dp[N][2][2])
i번째 비트를 보고 있을 때,x의i번째 글자가a,y의i번째 글자가b인 경우, 바꾼 비트 개수의 최솟값
dp[i][0][0]은 이전 비트가
(x[i - 1], y[i - 1]) = (0, 0)(x[i - 1], y[i - 1]) = (1, 0)
둘 중 하나이어야 한다.
만약 (x[i - 1], y[i - 1]) = (0, 1)인 경우, y[i - 1]가 1이므로 i - 1번째까지 1이 홀수개 있었다는 의미인데, x[i]가 0이므로 1의 개수가 바뀌지 않아 y[i]는 y[i - 1]와 같은 값인 1이어야 하기 때문이다.
또한 같은 논리로, 만약 (x[i - 1], y[i - 1]) = (1, 1)인 경우, y[i - 1]가 1이므로 i - 1번째까지 1이 홀수개 있었다는 의미인데, x[i]가 0이므로 1의 개수가 바뀌지 않아 y[i]는 y[i - 1]와 같은 값인 1이어야 하기 때문이다.
비슷한 방식으로 나머지 상태도 업데이트 할 수 있다.
dp[i][0][1]은 이전 비트가
(x[i - 1], y[i - 1]) = (0, 1)(x[i - 1], y[i - 1]) = (1, 1)
둘 중 하나이어야 한다.
dp[i][1][0]은 이전 비트가
(x[i - 1], y[i - 1]) = (0, 1)(x[i - 1], y[i - 1]) = (1, 1)
둘 중 하나이어야 한다.
dp[i][1][1]은 이전 비트가
(x[i - 1], y[i - 1]) = (0, 0)(x[i - 1], y[i - 1]) = (1, 0)
둘 중 하나이어야 한다.
이전 상태를 참조할 때, 현재 상태에 맞게 비트 업데이트 횟수를 추가해줘야 한다.
예를 들어, (x'[i], y'[i]) = (1, 0)인데, (x[i], y[i]) = (0, 0)으로 업데이트한다고 하자.
그러면 x[i]는 뒤바뀌어야 하므로 1을 추가해주어야 한다.
업데이트가 끝난 후에는 min(dp[n][0][0], dp[n][1][0], dp[n][0][1], dp[n][1][1])을 출력해주면 된다.
시간 복잡도는 O(NT)이다. (T는 테스트케이스의 개수, N은 문자열의 길이)
정답 코드
INF = int(1e9)
def check(a, b):
cnt = 0
for i in range(len(a)):
if a[i] != b[i]:
cnt += 1
return cnt
def solve():
x = " " + input()
y = " " + input()
n = len(x) - 1
dp = [[[INF, INF], [INF, INF]] for _ in range(n + 1)]
dp[1][0][0] = check("00", x[1] + y[1])
dp[1][1][1] = check("11", x[1] + y[1])
for i in range(2, n + 1):
c = x[i] + y[i]
dp[i][0][0] = min(
dp[i][0][0],
dp[i - 1][0][0] + check("00", c),
dp[i - 1][1][0] + check("00", c),
)
dp[i][0][1] = min(
dp[i][0][1],
dp[i - 1][0][1] + check("01", c),
dp[i - 1][1][1] + check("01", c),
)
dp[i][1][0] = min(
dp[i][1][0],
dp[i - 1][0][1] + check("10", c),
dp[i - 1][1][1] + check("10", c),
)
dp[i][1][1] = min(
dp[i][1][1],
dp[i - 1][0][0] + check("11", c),
dp[i - 1][1][0] + check("11", c),
)
print(min(dp[n][0] + dp[n][1]))
t = int(input())
for _ in range(t):
solve()마무리
경우의 수가 4가지이고, 각 상태마다 또 고려해야 하는 경우의 수가 2가지, 비트 비교하여 다른 개수만큼 더해줘야 하는 문제인데, 케이스 분류와 비트 비교 같은 것을 함수화하지 않으면 코드가 많이 복잡해졌을 것이라고 생각한다.
이 문제는 못 맞췄더라도 / 꼭 시도하지 않아도 DP 배열 설계나 상태 전이 점화식만 설계해봐도 좋을 거 같다.
댓글 남기기