출처
https://www.acmicpc.net/problem/20365
결과
문제
neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한다. 일우는 각 문제를 칠할 때 아래와 같은 과정을 한 번의 작업으로 수행한다.
- 연속된 임의의 문제들을 선택한다.
- 선택된 문제들을 전부 원하는 같은 색으로 칠한다.
예를 들어, 각 문제를 위와 같은 색으로 칠하려고 할 때, 1~2번 문제를 파란색, 3번을 빨간색, 4번을 파란색, 5번을 빨간색, 6~7번을 파란색, 8번을 빨간색으로 칠하는 작업을 순서대로 수행하면 6번의 작업을 거쳐야 한다. 하지만, 1~7번 문제를 파란색, 3번을 빨간색, 5번을 빨간색, 8번을 빨간색으로 순서대로 칠한다면 작업 횟수는 4번으로 가장 적다.
일우는 매일 500,000문제까지 시도하기 때문에, 이 작업이 꽤나 귀찮아지기 시작했다. 그래서 가장 효율적인 방법으로 위 작업을 수행하기를 원한다. 일우를 도와 각 문제를 주어진 색으로 칠할 때 필요한 최소한의 작업 횟수를 구하는 프로그램을 작성하라.
입력
첫째 줄에 색을 칠해야 하는 문제의 수 N (1 ≤ N ≤ 500,000)이 주어진다.
둘째 줄에 N개의 문자가 공백 없이 순서대로 주어진다. 각 문자는 i번째 문제를 어떤 색으로 칠해야 하는지를 의미하며, R은 빨간색, B는 파란색을 나타낸다. 그 외에 다른 문자는 주어지지 않는다.
출력
첫째 줄에 일우가 주어진 모든 문제를 원하는 색으로 칠할 때까지 필요한 작업 횟수의 최솟값을 출력하라.
예제 입력
6
BRBBRR
8
BBRBRBBR
6
BRRRRB
예제 출력
3
4
2
해석
매번 새로운 색이 나올 때 마다 칠하는 것보다 최소로 칠하는 방법은 한 색깔로 모두 칠한 다음에 다른 색으로 남은 부분을 칠하는 것이다. 그러나, 어떤 색깔로 한 번 다 칠할것인지는 모르므로, 2번을 계산하여야 한다.
일단, 글자들을 축소시킨다. BRRB처럼 R이 2번 연속나는 경우는 R 한개로 축소시킨다. 그러면 BRB가 된다. 이것을 최소로 칠하는 방법은 B로 모두 칠한 다음에 R 개수만큼 개수를 더해주면 된다. 즉, R개수 + 1개(모두 B로 칠하는 횟수)이다. 반대로 RBR이면, B개수 + 1개(R로 모두 칠한 횟수)이다. 이런식으로 정답을 구하면 된다.
소스 코드
1
2
3
4
5
6
7
8
9
10
|
import sys
n = int(sys.stdin.readline())
li = list(x for x in sys.stdin.readline().strip())
word = li[0]
for i in li:
if word[-1] != i:
word += i
r = word.count("B")
print(min(r + 1, len(word) - r + 1))
|
cs |
'백준 > lv.3' 카테고리의 다른 글
[lv3] 1932. 정수 삼각형(Python 파이썬 풀이) (0) | 2021.08.16 |
---|---|
[lv3] 21758. 꿀 따기(Python 파이썬 풀이) (0) | 2021.08.16 |
[lv3] 4358. 생태학(Python 파이썬 풀이) (0) | 2021.08.08 |
[lv3] 2075. N번째큰수(Python 파이썬 풀이) (0) | 2021.08.08 |
[lv3] 2493. 탑(Python 파이썬 풀이) (0) | 2021.07.31 |