[백준] 20365 블로그2 [풀지못했던 이유 + 코드]

그리디 & 구현

https://www.acmicpc.net/problem/20365

20365번: 블로그2

 

코드

import sys
from collections import Counter
import copy
input = sys.stdin.readline

n = int(input())
col = list(map(str, input().strip()))
dic = Counter(col)

mainColor = [k for k ,v in dic.items() if max(dic.values()) == v][0]
s = [col[i] for i in range(n) if col[i] != col[i-1] and col[i]!=mainColor]
print(len(s)+1)

 

설명

[잘못된 풀이]

해당 문제는 그리디 유형의 문제로 파악된다. 처음 시도했을 때는 해당 문제의 "문제가 원하는 방향"은 해석을 정확히 했다고 보았다. 문제에서 구하고자 하는 목표는 결국 아래와 같다.

 

 

"각 문제를 주어진 색으로 칠할 때 필요한 최소한의 작업 횟수를 구하여라"

 

 

 색을 칠하는 행동 자체를 힘으로 생각했다. 이것은 곧 내가 '색을 직접 칠해야 된다.' 두 개의 색깔이 주어졌기 때문에 두 색을 가지고 칠하는 경우를 좀 생각해 보면 R, B 두 가지 색상 중에서 '가장 많은 색상을 우선적으로 칠해버리고 적은 색상의 색을 칠하게 되면 되지 않을까' 이 뜻은 곧 '둘 중 칠해야 되는 횟수가 더 많은 색상을 기준으로 먼저 색칠한다.' 그리고 이후 예시조건을 보고 많이 애매모호했다. 우선 첫 번째 예시 조건 같은 경우에는 6번의 작업을 거쳐야 하는 경우를 설명해주고 있으며 해당 조건을 보고 파악해야 할 것은 아래와 같다.

 

 

"연속해서 칠하고 있다" 그리고 "연속되지 않은 것도 칠하고 있다."

 

 

 그러면 연속된 색상의 문제 같은 경우는 '1회'로 계산하고 있다. 그리고 연속되지 않은 것도 '1회'로 계산하고 있다. 여기서 중요한 포인트는 연속되어진 색상 같은 경우는 1회로 계산해야 된다는 것이다. 처음 이 사실을 간과한 채로 문제를 풀어나가기 시작했다.

이후 두 번째 예제 조건에서 요구하고 있는 내용은 1~7번 문제를 파란색으로 칠하고 있다는 문장이다. 이 문장에서 해석을 잘못해서 처음에 오답을 냈었다. 오답의 내용으로는 "색상을 가장 많이 가진 구간을 찾고자 했던 것"이다. 하지만 이는 문제에서 요구하는 내용이 아니었다. 왜 이런 생각을 했었냐면 1~7번에 집중했기 때문이다. 먼저 가장 많은 색상을 사용하는 색의 시작점과 끝점까지의 구간 중에서 가장 많이 해당 색상을 포함하는 구간을 찾고자 했었고 그 구간 내에서 해당 색상을 칠해버리고 그 칠해버린 구간을 연속으로 생각한 뒤 이후에 반대되는 색상을 찾아서 카운트해 주었던 것이다. 이렇게 생각하면 첫 번째 예제에서도 반례가 나올 수 있다.

 

 

BBRBRBBR

 

 

위 예제 같은 경우 만약 '잘못된 접근'으로 생각해 본다면 B가 가장 많은 색상을 사용하기 때문에 첫 시작점에 B가 존재하고 길이의 - 1 지점까지 B가 존재하며 그 구간에서 가장 많이 B를 포함하는 구간을 찾는 것이다. 이후 반대되는 색상을 칠해준뒤 남은 부분은 B가 아닌 부분이기 때문에 칠해주어야 하는 부분이며 전체에서 - 해당구간을 뺀 수를 더해준다는 것이다. 최종적으로 가장 많이 포함된 구간은 칠했기 때문에 +1까지 한다면 출력에 대한 답은 맞았지만 '올바른 풀이법이 아니다.' 이 생각에 반례가 되는 점을 생각해본다면

 

1. 연속된 구간을 간과하고 있다.

2. 전체에서 - 해당구간을 뺀 나머지 구간에서도 연속된 구간이 나올 수 있으며, 마지막 구간 같은 경우 그 이전이 만약 R이라면 즉

 

"BBRBRBRR"

 

이라고 한다면 B까지 한번 칠했으니 +1 해당 구간에서 B로 칠했기 때문에 바꿔 주어야 하는 색상의 개수는 2개 +2
그리고 나머지 구간 전체에서 나머지 구간을 뺀 "RR" 부분이다.

(1) 번의 연속된 구간을 간과하고 있기 때문에 이 구간은 +2로 계산이 되게 된다.

비슷한 발상으로 맨 앞에 "RR"인 경우다.

"RRBBRBRBBR"

해당 경우 또한 첫 번째 구간에서 R이 연속되게 나올 수 있기 때문에 답이 틀리게 나오게 된다. 그래서 여러 사람들의 풀이를 참고하며 생각해 본 결과 발상이 참 신기 하면서도 문장을 보고 해석하는 능력이 뛰어난 사람이 많구나 싶었다.

 

[올바른 풀이]

우선 1~7번 구간의 문장을 곱씹어 보면 1~7번 까지를 파란색으로 칠하고 있다는 건 두 색 중에서 가장 많이 칠해지는 색상으로 칠하고 있다는 걸 알 수 있다. 또한 1회로 계산되고 있다는 것을 문장에서 보여주고 있다. 그렇다면 이제 그 구간을 이미 칠했다는 것으로 본다면 +1회가 말이 된다. 왜냐하면 1~7번 까지를 같은 색으로 연속된 부분을 생각해서 칠하게 되면 그 부분은 "1~7번까지를 파란색으로 칠한다"라고 볼 수 있다. 만약 이를 조금 다르게 해석해 본다면 전체를 전부 파란색으로 칠한 다음에 그 구간에서 연속된 반대되는 색상을 찾아서 카운트해 주면 된다. 그리고 원래 색상과 같아야 하니까 그 색상을 원래의 색상으로 바꾸어 주는 작업으로도 생각해 볼 수 있는데 사실 이 방법은 결국 파란색으로 연속된 부분을 미리 칠했다고 가정하고 빨간색의 연속된 부분을 카운트해주면 되는 부분이다. 따라서 이번 문제에서 핵심적으로 생각해야 될 부분은 '연속적으로 선택하는 것', '같은 색으로 칠하는 것' 결국 그럼 카운트하게 될 때 반대되는 색상에서 이전 색상과 다르다면 카운트를 해주면 되고 만약 이전 색상과 같은 색이라면 연속된 색상이기 때문에 카운트하지 않게 된다면 연속된 부분을 생각하면서 카운트하게 된다. 또한 앞서 미리 선택했던 가장 많이 사용하는 색상이 아닌 색상으로 판단을 해야 된다는 것까지 해서 정답 판정을 받았지만 그리디 유형의 문제는 언제나.. 문제의 방향성을 이해하는 것에 그치는 게 아닌 문제를 풀어낼 방법을 다양한 아이디어로 시도해 보는 연습이 중요한 것 같다.