[백준 1011] Fly me to the Alpha Centauri

오랜만에 문제 몇개 풀다가 올려봐용.

일단 이 문제를 풀기 위해서 저는 그냥 그림을 그려봤습니다.

x y 가 0 11 인 상황의 그림을 봐볼게요

(x는 start로, y는 end로 하겠습니다)

처음 출발은 1칸으로 출발시킨다고 문제 그림에 나와있고, 도착도 1칸으로 도착해야된다 써있습니당

그래서

1. start와 end부터 번갈아가며 점프를 1칸,

2. 점프 후 사이에 거리가 있다면 점프를 1칸 늘려서 다시 start와 end에 번갈아서 해줍니다.

( 점프 횟수가 최소이여야 하기 때문에 최대한 뛸수있는 만큼 뛰어야함)

이렇게 진행하면 그림처럼 두개의 위치가 겹쳐버리는 곳이 생깁니다.

그럼 다시 그림의 맨 밑 박스상황에서 남은 점프거리가 2일 경우로 가서,

남은 2칸은 앞에서 3칸을 뛰었기 때문에 2로 정상적으로 뛰면 해결이 됩니다. ( 1 2 3 2 2 1 )

그럼 입력이 0 10 일경우 마지막 그림이 빈 사각형이 1개가 남게되는데

1 2 3 1 2 1 이렇게 뛰지 못하기 때문에 햇갈릴 수 있는데

이 부분은 지금 문제에서는 중요한부분이 아니게됩니다.

1칸이 남으면 end에서 처음 1칸 뛰었을때 지금 남은 1칸을 뛴다고 생각하면 되기 때문입니다.

이게 점프를

어떻게 뛰냐 문제가 아니라

몇번 뛰었냐를 물어보는 문제이기 때문에

start 1 2 3 1 2 1 end 가 아닌

start 1 2 3 2 1 1 end 이렇게 진행된다고 생각하고 문제를 풀면 됩니다요

소스코드

FLOW