[백준] 20365 블로그2

문제

• N개의 문제가 있다. 해결한 문제는 파란색(B), 해결하지 못한 문제는 빨간색(R)으로 표현한다.
• 문제를 칠할 때는 연속된 임의의 문제들을 선택하고, 선택된 문제들을 전부 원하는 같은 색으로 칠한다.
• 가장 효율적으로 색을 칠하는 최소 작업 횟수 구하기

 

• 1 <= N <= 500,000

 

풀이

• 전체를 한 번에 첫 문제와 같은 색으로 칠한 뒤 사이에 있는 다른 색을 다시 바꿔준다.
  • rb -> 첫 문제와 반대되는 색
  • cnt -> 전체를 한 번에 첫 문제와 같은 색으로 칠하므로 1로 시작한다.
  • 만약 색이 달라지는 구간이 나오면 다시 칠해야 하므로 cnt + 1 해준다.

 

N = int(input())
paint = input()

rb = 'B' if paint[0] == 'R' else 'R'
cnt = 1
for i in range(1, N) :
    if paint[i] == rb and paint[i-1] != rb :
        cnt += 1

print(cnt)

 

References

• 백준 그리디