17615번 볼 모으기

문제 설명

이번 문제는 빨강색, 파랑색 볼이 주어졌을 때, 다음과 같은 규칙으로 볼을 이동시켜서 같은 색의 볼들이 모여있도록 할 때의 최소 이동횟수를 구하는 문제입니다.

• 바로 옆에 다른 색의 볼이 있으면 그 볼들을 모두 뛰어넘을 수 있다.
• 옮길 수 있는 볼의 색은 한 가지이다. 처음에 빨간 볼을 움직였다면 다음에는 파란 볼을 움직여야 한다.

 

 

문제 풀이

아이디어

그림 1, 그림 2, 그림 3

그림 4

공을 최소 횟수로 움직일 수 있는 순서

공들을 움직일 경우 바로 옆의 다른 색의 볼은 모두 뛰어넘을 수 있다는 규칙이 있다.

이것을 만족하되, 공을 모으는 최소 이동횟수를 구하는 움직이는 순서는 가장 자리 쪽의 공을 먼저 움직이는 것이다.

 

그림 1에서 파란 색 공을 움직이는 상황을 살펴보겠습니다.

만약, 4번 공을 먼저 움직인다면 6번 앞에 5번에 위치하게 되며, 이동 횟수는 하나 사용하게 됩니다.

만약, 6번 공을 먼저 오른쪽 가장자리로 움직여주면, 4번 공은 한 번의 움직임으로 오른쪽 가장자리로 이동할 수 있게 됩니다.

차례로 3번 2번 공을 움직여 준다면, 공의 이동횟수는 파란 공의 개수 4가 될 것입니다.

 

그러므로 공을 최소 횟수로 움직이게 하는 순서대로 공을 움직이면, 움직이려는 색의 공의 개수만큼만 움직이면 됩니다.

 

더 적은 횟수로 이동하는 방법

문제에서 주어진 그림을 살펴보면 빨간색을 모으는 것이 더 이동횟수가 적다.

그 이유를 살펴보면 가장 오른쪽에 빨간색이 모여 있고, 따로 떨어져 있는 빨간 공의 개수가 더 적기 때문이다.

그렇다는 것은 가장자리에 위치한 공의 색과 동일한 공이 이어져 있을 경우 이어져 있지 않은 공들만 가장자리로 옮기면 된다는 것이다.

(위의 그림 1에서 빨간 공을 움직이는 것을 예시로 들자면, 7,8,9는 가장 자리에 이어져 있으므로 움직일 필요가 없고, 따로 떨어져 있는 1번 5번만 움직이면 된다.)

 

-> 가장자리의 공과 이어져 있는 같은 색의 공은 움직이지 않아도 된다. 따로 떨어져 있는 공들만 가장자리로 움직여 주면 된다.

 

예외

위의 아이디어에서 가장자리에서 떨어진 공들만 움직이면 최소 횟수라고 말했지만, 예외인 경우도 있습니다.

지금까지의 아이디어로 생각해보면, BBBRRB와 같은 상황을 살펴보면, 가장자리에 B가 있으므로 B와 같은 색의 1,2,3번째 B만 움직이는 것이 최소 횟수라 생각했습니다.

하지만, 여기서는 R이 2개이므로 R을 두개만 움직이면 최소횟수가 됩니다.

 

그러므로, 가장자리 볼과 같은 색이지만 떨어져 있는 볼들과 다른 색의 공의 개수를 비교해주어야 됩니다.

 

 

풀이 

변수 선언

ball = 문제에서 주어진 볼의 순서

last_ball = 가장 자리에 위치한 볼의 색

connected_ball_count = 가장자리에서 이어진 같은 색 볼의 개수

ball_count = 가장자리에 위치한 볼의 총 개수

flag = 가장자리에서 이어져 있는 볼의 개수를 세고 있는지 나타내는 값(boolean)

 

풀이 1

for문 반복문을 돌면서 마지막 볼과 이어진 같은 색의 볼들의 개수와 마지막 볼 색의 공의 총 개수를 구해줍니다.

 

여기서 예외 사항을 생각해보자면, 가장 자리 볼과 같은색이지만 따로 떨어져 있는 공의 개수(X)가 다른 색 공의 개수(Y)보다 적어야지만 X가 답이되고, 다른 색 공의 개수가 더 적다면, Y가 답이 됩니다.

 

이를 삼항 연산자로 나타내면 아래와 같습니다.

ball_count-connected_ball_count if ball_count-connected_ball_count<N-ball_count

 

풀이 2

위의 풀이법으로 제출을 하게 되면 서브 태스크 1만 정답이 됩니다.

그 이유는 문제의 조건 속에 있습니다.

• 바로 옆에 다른 색의 볼이 있으면 그 볼들을 모두 뛰어넘을 수 있다.

위 조건을 살펴 보면 바로 옆이라는 말은 그림 2,3,4와 같이 오른쪽만을 뜻하는 것이 아닌 왼쪽도 될 수 있으므로, 풀이 1을 왼쪽 가장자리에 대한 것도 진행해주면 답이 됩니다.

 

 

 

해결

이번 문제는 비교적 쉽게 풀었지만, 문제의 그림만 보고 판단해서 한 번 틀린 문제였습니다.

문제에서 주어진 그림과 규칙을 자세히 읽어야 될 것 같습니다.

 

문제 링크 : https://www.acmicpc.net/problem/17615

17615번: 볼 모으기

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/17615.py