(그리디) 백준 20365번 _ 블로그2 [Python]

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

20365번: 블로그2

전형적인 그리디 문제이다.

 

아래는 내가 처음 풀려고 했던 방식인데 "BRBBRR"의 정답이 3인데 자꾸 4를 출력했다.

a = "BRBBRR"
answer = 1
start = a[0]
for i in a[1:]:
  if start != i:
    answer += 1
    start = i

if a[0] == a[-1] and a.count(a[0]) == a.count(a[-1]) and answer != 1:
  answer -= 1

b = min(a.count('R'),a.count('B')) + 1

answer = min(b,answer)

print(answer)

 

일반화된 코드를 짜고싶어 'B', 'R' 등의 구체적인 색을 명시하고 싶지 않았으나, 다른 풀이들을 보니 대부분 사용하였다.

문제에서 경우의 수가 명확히 주어진 경우 일반화된 케이스까지 생각할 필요는 없는 것 같다. 주어진 문제나 잘 풀자!

 

정답 코드는 아래와 같다.

len = int(input())
string = input()

colors = { 'B' : 0, 'R' : 0 } # 색깔 별 횟수를 저장하는 딕셔너리
colors[string[0]] +=1 # 맨 처음엔 무조건 칠해야함
for i in range(1, len):
    if string[i] != string[i-1]: # 색이 바뀔때 "바뀐 색" 딕셔너리 1 추가
        colors[string[i]]+=1

result = min(colors['B'], colors['R'])+1
print(result)

# 아래 주석은 각각의 단어들에 대한 실행 결과다
'''
---------- BRBBRR ----------
현재 string[i]는 R ----> {'B': 1, 'R': 1}
현재 string[i]는 B ----> {'B': 2, 'R': 1}
현재 string[i]는 R ----> {'B': 2, 'R': 2}
result : 3
---------- BBBB ----------
result : 1
---------- BBRR ----------
현재 string[i]는 R ----> {'B': 1, 'R': 1}
result : 2
---------- BRBRBRBRB ----------
현재 string[i]는 R ----> {'B': 1, 'R': 1}
현재 string[i]는 B ----> {'B': 2, 'R': 1}
현재 string[i]는 R ----> {'B': 2, 'R': 2}
현재 string[i]는 B ----> {'B': 3, 'R': 2}
현재 string[i]는 R ----> {'B': 3, 'R': 3}
현재 string[i]는 B ----> {'B': 4, 'R': 3}
현재 string[i]는 R ----> {'B': 4, 'R': 4}
현재 string[i]는 B ----> {'B': 5, 'R': 4}
result : 5
---------- B ----------
result : 1
---------- BRRRRRBR ----------
현재 string[i]는 R ----> {'B': 1, 'R': 1}
현재 string[i]는 B ----> {'B': 2, 'R': 1}
현재 string[i]는 R ----> {'B': 2, 'R': 2}
result : 3
---------- BRBRRRRRRRRRRRRR ----------
현재 string[i]는 R ----> {'B': 1, 'R': 1}
현재 string[i]는 B ----> {'B': 2, 'R': 1}
현재 string[i]는 R ----> {'B': 2, 'R': 2}
result : 3
'''

 

• 딕셔너리를 이용하여 B와 R 각각의 색의 경우에 대해 다음 단어의 색이 바뀔때마다 1씩 추가한다.
• 이때, 문자열의 시작 색깔에 해당하는 곳은 1을 바로 덜해준다.
• string[i]가 "R"이면 딕셔너리에서 "R"에 해당하는 값에 1을 추가해주고, "B"면 "B"에 해당하는 값에 1을 추가한다.
• 마지막에는 각 색 별 횟수의 최소값을 min 함수로 찾아낸 후 1을 더해준다.
• 1을 더해주는 이유는 전체를 한번에 칠하는 것과 똑같다고 생각하면 된다.
  • 안 더해주면 색이 없는 상태에서 맨 처음부터 하나씩 시작하는 것과 똑같다.