[BOJ] 백준 1011번 Fly me to the Alpha Centauri c++

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

1011번: Fly me to the Alpha Centauri

출발점에서 도착점까지 이동장치를 이용하여 이동한다 했을때 이동 규칙은 다음과 같다.

바로 직전 이동거리가 k광년이면 이번에 이동 가능한 거리는 k-1, k, k+1 셋 중 하나이다.

음수 혹은 0거리만큼의 이동은 의미가 없다(이동 불가능 하다).

이러한 규칙으로 이동한다 했을때 공간이동 장치 작동 횟수의 최소값을 구하는 문제이다.

 

이러한 종류의 문제는 일단 가까운 거리부터 어떤방식으로 이동해야 가장 빨리 갈 수 있는지를 나열해 보면된다.

나열하다 보니깐 다음과 같은 규칙을 찾을 수 있었다.

작동 장치를 1번 쓰는 경우 갈 수 있는 거리 : 1(1) - 1개

작동 장치를 2번 쓰는 경우 갈 수 있는 거리 : 2(11) - 1개

작동 장치를 3번 쓰는 경우 갈 수 있는 거리 : 3(111), 4(121) - 2개

작동 장치를 4번 쓰는 경우 갈 수 있는 거리 : 5(1211), 6(1221) - 2개

작동 장치를 5번 쓰는 경우 갈 수 있는 거리 : 7(12211), 8(12221), 9(12321) - 3개

작동 장치를 5번 쓰는 경우 갈 수 있는 거리 : 10, 11, 12 - 3개

작동 장치를 6번 쓰는 경우 갈 수 있는 거리 : 13, 14, 15, 16 - 4개

작동 장치를 7번 쓰는 경우 갈 수 있는 거리 : 4개

작동 장치를 8번 쓰는 경우 갈 수 있는 거리 : 5개

.

.

.

장치를 2번씩 더 쓸때마다 갈 수 있는 거리가 1개씩 더 늘어나는것을 알 수 있었다.

이러한 규칙을 토대로 프로그래밍을 하면 다음과 같다.

코드 원본 : https://github.com/sbl133/BOJ/blob/main/%231101.cpp

GitHub - sbl133/BOJ

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!