[Python] 백준 17615) 볼 모으기

🔗문제 링크

17615번: 볼 모으기

✅ 문제 유형

구현

🤔 문제 풀이

백준의 알고리즘 분류는 그리디 알고리즘으로 되어 있지만 딱히 제 풀이는 그리디한 것 같지는 않습니다. 저는 문제에서 요구하는 바를 작은 문제로 나누고 작은 문제의 결과를 비교해 최종 해를 찾았습니다.

문제를 4개의 작은 문제로 나누었습니다.

i ) 정렬 결과가 RRRRBBBB , R공을 옮긴다.
ii ) 정렬 결과가 RRRRBBBB, B공을 옮긴다.
iii ) 정렬 결과가 BBBBRRRR, R공을 옮긴다.
iiii ) 정렬 결과가 BBBBRRRR, B공을 옮긴다.

이렇게 나눈 4개의 작은 문제들 중 공을 옮긴 횟수가 가장 작은 것이 최종 해가 됩니다. 그렇다면 작은 문제의 해는 어떻게 구할까요 ? case 1의 경우를 생각해봅시다. R이 왼쪽 B가 오른쪽에 정렬이 되어 있어야합니다. 만약 입력이 RRRBRBBB 라면 R공을 1번 옮기니 1이 될 것이고, 입력이 BBBRBRRR 라면 R공을 4번 옮겨야하니 4가 될 것입니다. 이를 통해 왼쪽부터 입력 문자열을 반복문을 통해 탐색했을 때 B가 한 번도 등장하지 않았다면 R공을 왼쪽으로 움직일 필요가 없습니다. 하지만 B가 한 번이라도 등장했다면 R공을 왼쪽으로 옮겨야 할 것입니다. 이를 코드로 나타내면 아래와 같습니다.

CNT = 100000000000
# i case

bit = 0
cnt = 0

for i in ball :
    if i == 'B':
        bit = 1
    if bit == 1 and i == 'R' :
       cnt += 1
CNT = min (cnt,CNT)
#print("i ", cnt)

위와 같은 방식으로 나머지 작은 문제를 해결한다면 최종 해를 구할 수 있습니다.

📖 코드

n = int(input())
ball = list(input())

# i ) RRRRBBBB R공 옮기기
# ii ) RRRRBBBB B공 옮기기
# iii ) BBBBRRRR R공 옮기기
# iiii ) BBBBRRRR B공 옮기기

CNT = 100000000000
# i case
bit = 0
cnt = 0

for i in ball :
    if i == 'B':
        bit = 1
    if bit == 1 and i == 'R' :
       cnt += 1
CNT = min (cnt,CNT)
#print("i ", cnt)

# ii case
bit = 0
cnt = 0
for i in range(n-1,-1,-1):
    if ball[i] == 'R':
        bit = 1
    if bit == 1 and ball[i] == 'B' :
        cnt += 1

CNT = min(cnt,CNT)
#print("ii ", cnt)

# iii case

bit = 0
cnt = 0
for i in range(n-1,-1,-1):
    if ball[i] == 'B':
        bit = 1
    if bit == 1 and ball[i] == 'R' :
        cnt += 1
#print("iii ",cnt)

CNT = min(cnt,CNT)

# iiii case
bit = 0
cnt = 0

for i in ball :
    if i == 'R':
        bit = 1
    if bit == 1 and i == 'B' :
       cnt += 1

#print("iiii ",cnt)
CNT = min (cnt,CNT)
print(CNT)