서론
본 포스팅 시리즈는 필자가 Baekjoon 문제를 풀면서 정리한 코드나 이론을 올리는 포스팅이다.
대부분의 설명은 코드의 주석으로 기재되어있으니 참고바란다.
문제
Baekjoon 1011번 - Fly me to the Alpha Centauri:
https://www.acmicpc.net/problem/1011
1011번: Fly me to the Alpha Centauri
우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행
www.acmicpc.net
해법
이번 문제는 주어진 X지점에서 Y지점까지 이동하기 위해 공간이동장치를 최소 몇번 작동시켜야 하는지를 구하는 문제이다. 이 공간이동장치를 작동시키는 조건으로 다음과 같이 제시되었다.
- 이전 작동시기에 k광년을 이동했을 때는 (k-1)광년, k광년 또는 (k+1)광년만을 다시 이동할 수 있다.
- 이 장치를 처음 작동시킬 경우 -1광년, 0광년 또는 1광년을 이론상 이동할 수 있으나, 사실상 0광년 이하 만큼의 이동은 의미가 없으므로 1광년을 이동할 수 있다
- 마지막 작동시엔 무조건 1광년만 이동해야한다.
정리하자면, 공간이동장치의 첫번째와 마지막 작동시엔 1광년만 이동할 수 있고 작동시 이동거리는 이전 작동시의 이동거리에 -1, 0, +1 이어야만 한다.
우리는 여기서 규칙성을 찾기 위해 경우의 수를 나열해보도록 하겠다.
위 표를 보면 거리가 어떤 임의의 수의 제곱인 경우, 이동과정이 "121", "12321", "1234321"과 같은 형태로 나타나게 된다(단, 3이하의 거리는 예외적으로 거리가 장치작동횟수와 동일하다.)
그리고 거리가 어떤 임의의 수의 제곱인 경우를 기준으로 나눠서 보면 각 구간에 있는 이동횟수의 경우의 수가 "(임의의 수)*2-1" 또는 "(임의의 수)*2-2"가 된다는 것을 알 수 있다(예를 들어, 거리가 25이하 17이상인 구간 안에는 이동횟수가 "5*2-1"(9) 또는 "5*2-2"(8)인 경우가 있다.)
풀이
'SW > Baekjoon' 카테고리의 다른 글
| [Baekjoon 문제풀이] 1934 - 최소공배수 (Python 3) (0) | 2022.01.06 |
|---|---|
| [Baekjoon 문제풀이] 4948 - 베르트랑 공준 (Python 3) (0) | 2022.01.06 |
| [Baekjoon 문제풀이] 11653 - 소인수분해 (Python 3) (0) | 2022.01.04 |
| [Baekjoon 문제풀이] 4153 - 직각삼각형 (Python 3) (0) | 2022.01.04 |
| [Baekjoon 문제풀이] 9461 - 파도반 수열 (Python 3) (0) | 2022.01.04 |