[백준 17615] 2019 정올 2차 초등부 "볼 모으기"

문제 출처 : https://www.acmicpc.net/problem/17615

17615번: 볼 모으기

이 문제는 2019년 정보 올림피아드 2차 대회 초등부 2번 문제 입니다.

알고리즘 이해하기

문제에는 제약 조건이 많기 때문에 잘 읽어봐야 합니다.

1. 한가지 색깔만 옮길 수 있습니다. 처음에 빨간색을 옮기면 계속 빨간색만 옮겨야 합니다.
2. 하나씩 옮기되, 최대한 멀리 옮겨야 최소 값을 얻을 수 있습니다.

이 두가지를 생각하면서 시뮬레이션 해보면 결국 우리가 만들 수 있는 경우는 총 4가지 경우중에 하나 입니다.

1. 빨간색 공을 모두 오른쪽으로 이동
2. 빨간색 공을 모두 왼쪽으로 이동
3. 파란색 공을 모두 오른쪽으로 이동
4. 파란색 공을 모두 왼쪽으로 이동

이렇게 4가지의 경우를 얻을 수 있고, 이 4가지 중에서 가장 숫자가 적은 경우가 답이 됩니다.

어느 공부터 옮길까?

빨간색 공을 오른쪽으로 이동하는 것부터 생각해 보겠습니다. 빨간색 공을 오른쪽으로 이동하기 위해서는 오른쪽 에 있는 빨간공부터 오른쪽으로 보내야 합니다. 왼쪽 공 부터 이동하면 이동 횟수만 늘어나게 됩니다.

위와 같이 오른쪽에 있는 빨간공부터 이동하면 2번만에 이동이 가능 합니다.

왼쪽에 있는 빨간공부터 이동하게 되면 간격이 파란색 볼이 뭉쳐있는게 줄지 않아 3번 이동해야 합니다.

이동 횟수 계산하기

다음으로 이동 횟수에 대해 생각해 보겠습니다. 빨간색 공이 오른쪽으로 이동할 때 처음부터 빨간색이면 이동을 하지 않습니다. 그러다가 파란색 공이 나오고 부터 한 번의 횟수로 원하는 위치에 이동하게 됩니다.

위 그림처럼 오른쪽 끝에 있는 오른쪽 빨간공은 이동하지 않습니다.

오른쪽 공이 이동할 때 한 번의 횟수로 제일 끝에 가는 것을 알 수 있습니다.

코드 작성하기

그럼 코드를 작성해 보겠습니다.

입력 받기

N = int(input())
ball = input()

볼의 개수 N을 입력 받습니다. 다음으로 볼의 색깔을 입력 받습니다.

결과 출력

a1 = solve('R', 1)
a2 = solve('R', -1)
a3 = solve('B', 1)
a4 = solve('B', -1)
print(min(a1, a2, a3, a4))

결과를 출력합니다. solve 함수를 통해 각각의 볼을 이동시킬 때 얻을 수 있는 최소 값을 리턴합니다. solve 함수에는 두개의 인자가 들어갑니다. 첫 번째는 원하는 볼의 색깔 입니다. 각각 R은 빨간색, B는 파란색을 뜻합니다. 다음으로 방향입니다. 1은 왼쪽으로 이동했을 때를 뜻하고, -1은 오른쪽으로 이동하는 경우를 뜻합니다. 이렇게 4가지 경우의 최소값을 얻어 그중에 가장 작은 값이 답이 되는 것입니다.

solve 함수

def solve(color, dir):
    cnt = 0
    check = False
    for b in ball[::dir]:
        if b != color and not check:
            check = True
        if b == color and check:
            cnt += 1
    return cnt

solve 함수 입니다. color는 색깔은, dir은 방향을 뜻합니다. 빨간색 공을 이동시킬 때 처음 나온 빨간색 공은 더하지 않았습니다. 이것이 check 변수의 역활입니다. 파란색 공이 나오기 전까지는 공을 세지 않습니다. 파란색 공이 나오면 check 를 True로 바꿔 지금부터 나오는 빨간색 공의 갯수를 찾으면 그 값이 바로 이동 횟수가 됩니다.

전체 코드

전체 코드 입니다.

N = int(input())
ball = input()

def solve(color, dir):
    cnt = 0
    check = False
    for b in ball[::dir]:
        if b != color and not check:
            check = True
        if b == color and check:
            cnt += 1
    return cnt

print(min(solve('R', 1), solve('R', -1), solve('B', 1), solve('B', -1)))