[백준 20365번] 블로그2 - (python)

문제 링크 : https://www.acmicpc.net/problem/20365

20365번: 블로그2

 

Idea

우선 문제에서 최소값을 구하라고 하고 있고 규칙만 찾으면 최솟값을 찾을 수 있을것 같은 느낌이 들었다.

좋아 보이는 방법을 적용했을때 그 방법이 local -> global 로 갈때도 적용된다면 Greedy 문제이다.

 

문제에서 연속된 문제들은 같은 색으로 한번의 칠로 칠할 수 있다고 했으므로 연속된 같은 색끼리 묶을 수 있다. 

 

 

 

총 6개로 묶을 수 있고 처음부터 이렇게 칠하면 6번의 작업을 통해 완성할 수 있다.

이런식으로 칠하는 방식은 칠할 수 있는 횟수의 최대가 된다.

 

 

 

그러면 만약 먼저 하나의 색으로 다 칠하고 다른 색이 있는 부분만 또 칠하면 어떻게 될까

 

 

우선 파란색으로 먼저 다 칠한 경우를 보자.

파란색으로 한번에 다 칠하고 빨간색이 있는 부분을 칠해주면 된다.

 

 

 

 

 

 

 

 

 

 

 

 

 

총 4번만에 작업을 완성할 수 있다.

 

 

빨간색으로 먼저 다 칠한 경우를 보자.

빨간색으로 한번에 다 칠하고 파란색이 있는 부분을 칠해주면 된다.

마찬가지로 총 4번만에 작업을 완성할 수 있다.

 

한가지 색으로 먼저 칠한 경우 작업 횟수가 모두 동일했지만 처음에 봤던 처음부터 같은 색의 묶음 별로

칠하는 것 보다는 훨씬 작업량이 줄어들게 된다.

 

예제에서 나온 그림의 경우는 두가지 색의 그룹 갯수가 동일했기때문에 둘다 같은 횟수인 4가 나왔지만

만약 파란색 그룹의 수가 더 많았다고 가정한다면, 빨간색으로 먼저 칠하고 파란색을 칠하는 것보다 파란색으로 칠하고

빨간색으로 칠하는 것이 더 작업량이 작다는 것을 알 수 있다.

 

따라서 무조건 한번은 둘중 하나의 색으로 통일해서 칠하는 횟수로 들어가고 

두 색중에 그룹수가 더 작은 색의 그룹 수만큼 더해주면 된다는 것을 알 수 있다.

 

 

풀이

Python

N = int(input())
color = list(input())

d = {"R":0,"B":0}

d[color[0]]+=1
prev = color[0]


for i in range(1,N):
    if color[i]!=prev:
        d[color[i]]+=1
        prev = color[i]


min_group = min(d["R"],d["B"])

result = 1 + min_group

print(result)