17615 볼 모으기

17615 볼 모으기 / c++ / Silver1 / 42분

문제 및 코드

풀이 과정

그리디 알고리즘

1. 빨간 공 ‘R’과 파란 공 ‘B’가 섞여 놓여있는 문자열이 주어졌을 때, 빨간 공과 파란 공을 같은 색끼리 (ex. RRBB) 모을 수 있는 최소 움직임 수를 출력하는 문제
   1. 한가지 색상의 공만 움직일 수 있다.
   2. 바로 옆에 다른 색의 공이 있으면 모두 뛰어 넘어 옮길 수 있다. (RBBBBR - > BBBBRR)
2. 문제는 ‘어떤 색’의 공을 ‘어느 방향’으로 ‘어떤 순서로’ 움직일 것인가가 중요했다.
3. 어떤 색을 옮길지는 정할 수 없어서 두 색깔을 모두 옮겨보고 그 중 작은 값을 취하기로 했다.
4. 어느 방향으로 옮길지는 양 끝에 더 많은 공이 있는 방향으로 옮기기로 결정했다.
   1. 예를 들어 RRBBBBBBBRRR이면, 여기서는 왼쪽 공을 오른쪽으로 옮기는게 더 적다 (2, 3)
5. 어떤 순서로 움직일지는 생각해보면, 움직일 방향의 끝에서 연속된 공들의 바로 다음 공부터 움직이는게 효율적이다.
   1. 예를 들어 RRBRBRRRR 이면, 움직일 방향을 오른쪽이 되고, 그러면 RRB’R’BRRRR 이 공이 오른쪽 연속된 공들의 바로 다음 공이 된다.
   2. 이 공을 움직여야 RRBBRRRR이 되서 이후 2번더 움직이면 정리가 가능하다.
   3. 만약 ‘R’RBRBRRR 을 움직이면 제일 비효율적이다. 그대로 R’R’BRBRRR이 되버리기 때문
   4. R’R’BRBRRR 을 움직이면 RB’R’RBRRR이 된다. 이러면 다시 최소 3번을 움직여야 정리가 가능해진다.
6. 여기까지 계산을 해보니, 최종적으로 ‘움직일 방향의 끝에서 연속된 공들을 제외한 나머지 움직일 색상의 공들의 수’가 최소 움직이는 수라는 결론이 나왔다.
7. 해결

회고

1. 처음엔 실제 공을 옮길 생각으로 움직이지 않을 색상의 공을 단축하는 로직을 추가했었는데, 풀다 보니 직접 움직일 필요가 없어서 지웠다.
2. 결국 이미 정돈된 공 이외의 공은 최소 1번을 움직여야 하고, 정돈된 공에서 가까운 순서대로 움직여야 하므로 그리디 알고리즘으로 풀 수 있는 문제였다.