블로그2(백준 20365)

💡 **Check Point !

( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가? ✓

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

---

난이도 체감

1. 최상

2. 상

3. 중

4. 하✓

---

이해도

1. 완벽히 이해✓

2. 다소 헷갈리는 부분들이 있음

3. 이해 못함

문제

neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한다. 일우는 각 문제를 칠할 때 아래와 같은 과정을 한 번의 작업으로 수행한다.

1. 연속된 임의의 문제들을 선택한다.
2. 선택된 문제들을 전부 원하는 같은 색으로 칠한다.

https://upload.acmicpc.net/72fda166-5e2c-42b4-a9c1-e52993a5c45e/-/preview/

예를 들어, 각 문제를 위와 같은 색으로 칠하려고 할 때, 1~2번 문제를 파란색, 3번을 빨간색, 4번을 파란색, 5번을 빨간색, 6~7번을 파란색, 8번을 빨간색으로 칠하는 작업을 순서대로 수행하면 6번의 작업을 거쳐야 한다. 하지만, 1~7번 문제를 파란색, 3번을 빨간색, 5번을 빨간색, 8번을 빨간색으로 순서대로 칠한다면 작업 횟수는 4번으로 가장 적다.

일우는 매일 500,000문제까지 시도하기 때문에, 이 작업이 꽤나 귀찮아지기 시작했다. 그래서 가장 효율적인 방법으로 위 작업을 수행하기를 원한다. 일우를 도와 각 문제를 주어진 색으로 칠할 때 필요한 최소한의 작업 횟수를 구하는 프로그램을 작성하라.

나의 풀이

N=int(input())
colors=input()
current_color=colors[0]
color_count={'B':0,'R':0}
for c in colors:
    if c!=current_color:
        color_count[current_color]+=1
        current_color=c
color_count[current_color]+=1
answer=1
if color_count['B']>color_count['R']:
    answer+=color_count['R']
else:
    answer+=color_count['B']
print(answer)

• ‘B’와 ‘R’이 연속되는 숫자만 파악하면 될 것이라고 생각했다. 즉 ‘B’와 ‘R’의 개수가 중요한 것이 아니라, 연속되어 같은 색깔로 칠해져 있다면 1번 칠해진 것으로 간주한다.(한꺼번에 칠할 수 있기 때문이다)
• 위 방식대로 센 ‘B’와 ‘R’의 개수를 color_count에 저장하여, 더 많은 색깔을 전체에 칠하는 것으로 가정하여 answer=1로 시작한다.
• 이 후, 더 적은 count를 갖는 색깔의 개수를 answer에 더해주면, 가장 적은 횟수가 나온다.