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

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

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

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

이 문제는 이렇게 푸는 것이 확실한 것 같지만 더 이상 풀이에 진전이 없어서 해답을 본 문제이다.. 내가 생각한 풀이는 맞았으나 이를 코드로 구현하기가 꽤나 까다로웠던 문제였다.

내가 생각한 풀이 - 1

시작 위치 x 목표위치 y가 어떻든 중요한건 이동해야 할 거리가 중요하다. 이에 따라서 이동방법이 달라지기 때문이다. 가령 시작위치 x : 1 목표위치 y: 11 인경우나 시작위치 1000001 목표위치 y: 1000011 가 최소로 이동하는 방법은 같다는 뜻이된다. 우선 이동해야 할 거리에 따라서 몇 번을 이동해야하며 어떻게 이동해야 하는지 살펴보자. 이렇게 풀이를 적다보면 해결책이 떠오르곤 한다.

이동거리 이동 방법 이동 횟 수 1 1 1 2 11 2 3 111 3 4 121 3 5 1211 4 6 1221 4 7 12121 5 8 12221 5 9 12321 5 10 123211 6 11 123221 6 12 123321 6

위의 표는 이동거리에 따른 최소한의 공간이동 장치 작동 횟수이다. 또한 생각해 볼점은 0광년으로 간다는 것은 의미 없는 짓이다. 이전 작동시기에 k광년을 이동하였을 때는 k-1 , k 혹은 k+1 광년만을 다시 이동할 수 있으므로 순차적인 수열이 구성이 될 것이다. 또한 최소로 이동해야 하기 때문에 가능하면 숫자가 커지는 것이 좋을 것이다. 또한 적당한 때에 속도를 줄여줘야 할 것이다. 이는 직전의 이동거리는 1광년이 되어야 하기 때문이다! 뭔가 이렇게 생각하면 풀릴것 같지만 진전이 없다..

풀이 참고

내가 접근한 풀이와 마찬가지로 이동거리에 따른 이동방법과 이동횟수를 쭉 나열한 풀이다.

이동거리 이동 방법 이동 횟수 1 1 1 2 11 2 3 111 3 4 121 3 5 1211 4 6 1221 4 7 12121 5 8 12221 5 9 12321 5 10 123211 6 11 123221 6 12 123321 6 13 1233211 7 14 1233221 7 15 1233321 7 16 1234321 7 17 12343211 8

여기서 주목해야 할 부분은 이동횟수가 바뀌는 부분이다.

이동거리가 제곱수인경우 최소이동횟수가 변한다. (빨간색 마킹)

이동방법이 대칭인 경우 최소이동횟수가 변한다. (노란색 마킹)

교차해서 2가지가 나타난다. ( 제곱수 -> 대칭 -> 제곱수 -> 대칭 -> .... )

이 부분을 파악했다면 어렵지만 코드로 구현을 할 수 있다.

구현 - 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 import java.util. Scanner ; public class p1011{ public static void main( String [] args) { Scanner sc = new Scanner ( System . in ); int T = sc.nextInt(); for ( int i = 0 ; i < T; i + + ) { int x = sc.nextInt(); int y = sc.nextInt(); int dist = y - x; System . out . println (solve(dist)); } } public static long solve( int d) { long answer = 0 ; if (d < = 3 ) return d; for ( long n = 1 ; ;n + + ) { if (n * (n - 1 ) < d & & d < = n * n) { answer = 2 * n - 1 ; break ; } if (n * n < d & & d < = n * (n + 1 )) { answer = 2 * n; break ; } } return answer; } } 문제 풀이에 있어서 중요한 것은 결국 이동거리이다 시작위치나 목표위치가 아니기 때문에 입력을 받는 즉시 거리를 구했고 거리에 따른 답을 생성해 놓도록 구현을 했다. 사실 아이디어만 캐치하면 나머지는 구현력이기 때문에 이 부분은 해설을 보지 말고 혼자서 구현해보도록 해보자.

from http://kbj96.tistory.com/34 by ccl(S) rewrite - 2021-09-19 07:02:06