Categories
Algorithm🧩
백준 📝
BookReview📕
CleanCode✨
Network 📨
Database 🗄
DevOps☁️
에러 일기📕
Etc💬
Fishy Fish 🎣
Spring🌱
[백준] 20365 블로그 2
백준 20365 블로그 2
문제
neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다.
그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한다.
일우는 각 문제를 칠할 때 아래와 같은 과정을 한 번의 작업으로 수행한다.
- 연속된 임의의 문제를 선택한다.
- 선택된 문제들을 전부 원하는 같은 색으로 칠한다.
입력
- 첫 번째 줄: 색을 칠해야 하는 문제의 수 N
- 두 번째 줄: N개의 문자 (R, B)
출력
일우가 주어진 모든 문제를 원하는 색으로 칠할 때까지 필요한 작업 횟수의 최솟값
해결 방식
Greedy 알고리즘
- 칠해야하는 색이 변할때 마다 카운트
예시
B, B, R, B, R, B, B, R
- B
- 파란색 카운트 = 1, 빨강 카운트 = 0
- B
- 이전 색과 같은 색
- 파란색 카운트 = 1, 빨강 카운트 = 0
- R
- 이전 색과 다른 색
- 파란색 카운트 = 1, 빨강 카운트 = 1
- B
- 이전 색과 다른 색
- 파란색 카운트 = 2, 빨강 카운트 = 1
- R
- 이전 색과 다른 색
- 파란색 카운트 = 2, 빨강 카운트 = 2
- B
- 이전 색과 다른 색
- 파란색 카운트 = 3, 빨강 카운트 = 2
- B
- 이전 색과 같은 색
- 파란색 카운트 = 3, 빨강 카운트 = 2
- R
- 이전 색과 다른 색
- 파란색 카운트 = 3, 빨강 카운트 = 3
- 파란색, 빨강색 중 작은 값 + 1한 값 출력
코드
n = int(input())
problems = input()
colors = {'B': 0, 'R': 0}
colors[problems[0]] += 1
for i in range(1, n):
if problems[i] != problems[i-1]:
colors[problems[i]] += 1
print(min(colors['B'], colors['R']) + 1)
