[그리디 알고리즘 Lv.01] 11034번 캥거루 세마리2

 

1. 문제
    캥거루 위치 바꾸기 문제 (링크 참고)

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

11034번: 캥거루 세마리2

 

2. 문제 포인트

• 캥거루는 3마리의 위치를 입력 받는다
• 캥거루가 뛰는 위치는 다른 캥거루 2마리 사이다
  • 사이 좌표는 무관하다 (문제 조건에서 최대 가능 횟수를 묻기 때문에 최적의 위치로 생각한다)
• 최대 캥거루의 점프 횟수를 출력한다

 

3. 접근법

• 캥거루의 점프 횟수 규칙 찾기
  
  

• 첫번째 Case
  • '캥1'과 '캥2' 사이에는 공간이 없기에 이동이 불가능
  • '캥2'와 '캥3' 사이에 공간이 한개이기에 한번만 이동 가능
• 두번째 Case
  • '캥1'과 '캥2' 사이에 공간이 존재 (1칸)
    '캥1'과 '캥2' 사이에 '캥3'이 오게 되면 이동 횟수 1회로 종료
  • '캥2'와 '캥3 사이에 공간(2칸)으로 '캥1'이 이동
    위의 이미지와 같이 '캥1'이 최적의 위치로 이동하게되면 총 이동 가능 횟수 2회로 종료
  • 결과적으로 "최대 이동 가능 횟수 = max((캥1 위치 - 캥2 위치), (캥2 위치 - 캥3 위치)) - 1"

 

 

반응형

 

 

4. 결과 코드

import sys

while True:
	
    # 캥거루 위치값 입력 받기
    a = list(map(int, sys.stdin.readline().split()))
    
    # While을 이용해 입력이 더이상 없으면 종료
    if len(a) < 1:
        break
    
    # 1,2번 캥거루의 간격 차이와 2,3번 캥거루 간격 차이중 max값
    result = max(a[1] - a[0], a[2] - a[1])
    
    # 차이에서 -1한 값을 출력
    print(result - 1)