Greedy_12_블로그2(20365)
Greedy12블로그2(20365)
문제
neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한다. 일우는 각 문제를 칠할 때 아래와 같은 과정을 한 번의 작업으로 수행한다.
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는 파란색을 나타낸다. 그 외에 다른 문자는 주어지지 않는다.
출력
첫째 줄에 일우가 주어진 모든 문제를 원하는 색으로 칠할 때까지 필요한 작업 횟수의 최솟값을 출력하라.
풀이
- red 와 blue 모두 count 하여 최솟값 출력
- 주의할 것은 인덱스가 0인 경우와, 연속된 문자의 경우 count 하지 않는 것.
코드
import sys
def input():
return sys.stdin.readline().rstrip()
N = int(input())
str = input()
red = 0
blue = 0
for i in range(N):
if i == 0:
if str[i] == 'R': red +=1
if str[i] == 'B': blue += 1
else:
if str[i]=='R' and str[i-1]=='B':
red+=1
if str[i]=='B' and str[i-1]=='R':
blue+=1
print(min(red,blue)+1)
배운 것
string 은 count 라는 메서드로 안에 특정 문자열이 있는지 확인할 수 있다.
코멘트
원래 할려고 했던 코드
import sys
sys.stdin = open("input.txt","rt")
def input():
return sys.stdin.readline().rstrip()
N = int(input())
str = input()
blue = str.count('B')
red = str.count('R')
cnt = 1
if blue > red:
# 파란색 죄다 칠함
for x in range(1, N):
if str[0] == 'R':
cnt += 1
if str[x] == 'R' and str[x-1] == 'B':
cnt += 1
elif blue < red:
# 삘긴색 죄다 칠함
for x in range(1, N):
if str[0] == 'B':
cnt += 1
if str[x] == 'B' and str[x-1] == 'R':
cnt += 1
print(cnt)
count 로 빨 파 중 더 큰 문자를 냅두고 작은 문자를 count 하려고 했으나
모순이 있다.
"빨 파 빨 파 빨 파 빨 파파파파파파파파파파파 빨 "
인 경우에 [파]가 더 많으므로 파가 아닌 [빨]을 count 할 텐데, 이럼 최솟값이 아님
따라서 blue 와 red 둘다 count 하여 min 값을 출력하는 것이 옳다
Author And Source
이 문제에 관하여(Greedy_12_블로그2(20365)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@angel_eugnen/Greedy12블로그220365저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)