백준 20365 - 블로그2 (파이썬)

https://www.acmicpc.net/problem/20365

분류 : 그리디

https://www.acmicpc.net/problem/20365

풀이

이 문제는 그리디 알고리즘을 활용하여 최소한의 작업 횟수로 문제들을 원하는 색상으로 칠하는 방법을 찾는것이다.

주어진 문자열 S에서 연속된 같은 색상의 블록을 그룹화 하여 최소한의 횟수로 전체를 칠 할 수 있도록 해야한다.

8
BBRBRBBR

예시로 위와 같은 예제가 있다면 색상을 그룹화 하면 다음과 같다.

BB | R | B | R | BB | R

즉, B 그룹: 3개, R 그룹: 3개

이 경우, 한쪽 색상만을 먼저 칠하고, 나머지를 한 번에 칠하는 것이 최소 작업 횟수를 보장한다.

문제 풀이의 주요한 알고리즘

• 연속된 같은 색상을 하나의 그룹으로 압축
• 압축된 그룹에서 B 그룹과 R 그룹의 개수를 계산
• 최소한의 작업 횟수는 (더 적은 그룹 수 + 1)

코드

# 백준 20365 - 블로그 2
# 분류 : 그리디

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

T = ""
for i in range(N) :
    if i == 0 or S[i] != S[i - 1] :
        T += S[i]

blue = 0
red = 0
for i in range(len(T)) :
    if T[i] == "B" :
        blue += 1
    else :
        red += 1

if blue < red :
    print(1 + blue)
else :
    print(1 + red)