[BOJ][Python]11034 풀이

오랜만에 파이썬 풀이입니다. 그리디 연습이나 좀 할까 싶어서 난이도 낮은 것 부터 풀어보려구요.

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

11034번: 캥거루 세마리2

사실 이 문제는 굳이 그리디를 사용하지 않아도 됩니다. 그래서 그리디를 사용하지 않는 풀이와 그리디를 사용하는 풀이를 둘 다 보여드릴까 해요. 먼저 단순 추론으로 풀 수 있습니다. 문제의 조건이 타이트하게 설정되어 있기 때문에 딱히 예외적인 상황이나 함정이 없죠. 집중해서 볼만한 조건은 '한 번 움직일 때, 바깥쪽의 두 캥거루 중 한 마리가 다른 두 캥거루 사이의 정수 좌표로 점프한다. 한 좌표 위에 있는 캥거루가 두 마리 이상일 수는 없다' 입니다. 즉, 캥거루는 무조건 정수 좌표에, 겹쳐서는 있을 수 없는것이죠. 또한 사이의 정수 좌표로 점프한다는 문장으로 부터 사이이기만 하면 착지 좌표는 무엇이든 상관없다는 사실을 알 수 있습니다. 그렇다면 간격이 넓게 떨어져 있어도 중간 캥거루의 바로 옆으로 착지하면 계속해서 사이 공간이 1씩 줄어들어가는 점프로만 작업이 일어난다는 얘기와 같죠. 잠깐 그림으로 볼까요.

이런식으로 딱 붙어서 착지를 하는 걸 반복하는 과정이 되는 것이죠. 그 말은 곧 케이스당 최대 점프 횟수는 두 간격 중 넓은 간격 - 1 과 동일해집니다. 이게 약간 이해가 잘 안된다면 직접 그려가면서 해보고 넓은 간격 - 1과 같은 값이 나오는지 확인해보면 이해가 될 겁니다. 그럼 이제 코드를 볼까요.

while 1:
    try:
        a,b,c = map(int, input().split())
        print(max(b-a-1, c-b-1))
    except:
        break

코드는 너무 간단하죠. 다만 입력이 끝났음을 표시하는 조건이 더 이상 입력이 없는 것이기 때문에 EOF를 명시해줘야 합니다. 파이썬은 try - except 구문으로 처리할 수 있습니다.

 

이번에는 그리디 알고리즘으로 작성해보겠습니다. 그리디 알고리즘은 지금 순간에 최적의 판단을 하는 알고리즘이죠. 예를 들어서 뷔페에서 외식을 할 때 나중에 더 맛있는게 나오든 말든 지금 눈 앞에 있는 음식을 최대한 많이 담아 먹는게 그리디 알고리즘이라고 볼 수 있겠습니다(사실 뷔페 마케팅 전략에도 단가가 비싼 요리일수록 안쪽에 배치하는 전략이 있다고 합니다. 사람도 그리디 알고리즘을 따른다고 봐야할까요ㅎㅎ). 이번 문제에 비교를 해보자면 나중 일은 어떻게 될지 모르겠지만 일단 간격이 넓은 곳으로 점프하겠다 라는 알고리즘을 짜주시면 되겠습니다. 이번엔 코드를 보면서 설명을 좀 드려볼까요.

while 1:
    try:
        ans = 0
        a,b,c = map(int, input().split())
        while 1:
            if b-a <= 1 and c-b <= 1:
                print(ans)
                break
            if b-a > c-b:
                c = b-1
                c, b = b, c
                ans += 1
            else:
                a = b+1
                b,a = a,b
                ans += 1
    except:
        break

입력을 받는 것 까지는 위에 있던 코드와 동일합니다. 다만 내부 함수에서 반복문을 사용해서 더 이상 점프할 수 없을 때 점프한 횟수를 출력하는 코드가 있고, 그 아래에는 간격이 넓은 곳을 선택해서 점프를 하고 다음 연산을 쉽게 하기 위해 값을 바꿔주는 코드가 들어가 있습니다. 다만 해당 코드는 과정을 그대로 코드로 옮기기 위해서 어느 정도는 비효율적으로 작성되었다는 사실을 잊지마시고 본인만의 방법으로 최적화를 시켜보는 재미도 있을 것 같네요.