백준 33989 벚꽃과 단풍 / python

문제 : 33989

풀이 point

탐색하는 칸 기준으로 왼쪽은 모두 B 오른쪽은 모두 D로 만들 수 있는 최소 값을 찾아가면 된다. 예를 들면, 문자열이 BDBBDBD 일때 0번째 인덱스에서 왼쪽은 모두 B, 오른쪽은 모두 D로 바꿀 때 바꾸는 비용은 3이다. 2번째 인덱스는 2, 3번째 인덱스에서도 2이다.
이런식으로 문자열을 첫번째 인덱스부터 마지막 인덱스까지 보며 가장 적은 비용으로 바꿀 수 있을 때를 구해야한다. 다만 매 인덱스마다 왼쪽 오른쪽을 보는 것은 O(n^2)이다. 따라서 미리 값을 구해놓고 누적으로 진행해야한다.

풀이 방법

누적으로 진행하기 위해서 맨 처음 문자열에서 B의 개수를 알아낸다. 그 다음 문자열을 왼쪽에서 오른쪽으로 옮겨가며 D이면 d를 증가시키고 b이면 b를 증가시킨다. 이때 미리 구해둔 B의 개수에서 지금까지 인덱스에서의 b개수를 빼면 지금 인덱스 기준 오른쪽에 있는 B의 개수를 구할 수 있다. 이 B의 개수만큼 D로 바꿔줘야한다. 또한, D도 B로 바꿔줘야한다.(왼쪽은 B, 오른쪽은 D로 바꿔야하기 때문) 때문에 비용 값은 d+(B-b)가 된다. 이 값이 최소가 되는 값을 알아내면 된다.

풀이 코드

N = int(input())
S = input()

B = 0

for ch in S:
  if ch == 'B':
    B += 1

b, d = 0, 0

ans = B
for ch in S:
  if ch == 'D':
    d += 1
  else:
    b += 1
  ans = min(d + (B-b), ans)

print(ans)