✓

태그:

8. 기본 수학 1

두 행성를 이동하는 우주선이 일정 규칙으로 움직인다고 했을 때 최소로 걸리는 시간을 구하는 문제입니다. 문제의 조건을 분석해보면 이전 타임스탬프에 가졌던 속도의 ±1 범위에서 새 속도를 정할 수 있다는 것입니다. 이 규칙을 만족하면서 최소의 시간으로 이동하는 방법은 출발할 때부터 계속 속도를 올리거나 유지하다가 일정 구간부터 속도를 계속 줄여서 도착지에 도착하게끔 하는 것입니다. 즉 속도 변화량의 부호가 단 한 번만 바뀌어야 하는 것이죠. 그리고 가능한 한 속도를 유지하는 경우는 없게끔 해야 같은 시간에 가장 먼 거리를 이동할 수 있을 것입니다. 이 규칙을 적용시킬 때 어떻게 움직여야 하는지 열 개만 해보겠습니다.

1	2	3	4	5	6	7	8	9	10
1	1,1	1,1,1	1,2,1	1,2,1,1	1,2,2,1	1,2,2,1,1	1,2,2,2,1	1,2,3,2,1	1,2,3,2,1,1
1	2	3	3	4	4	5	5	5	6

이제 거리와 배열의 길이의 관계를 찾아보겠습니다. 먼저, 배열의 길이가 2n-1일 때 규칙을 만족하면서 가장 멀리 갈 수 있는 거리를 생각해봅시다. 1, 2, … , n-1, n, n-1, … , 2, 1의 속도로 이동했을 때 n²의 거리를 갈 수 있을 것입니다. 이제 배열의 길이가 2n일 때의 최대 거리를 생각해봅시다. 1, 2, … , n-1, n, n, n-1, … , 2, 1의 속도로 이동했을 때 n²+n의 거리를 갈 수 있습니다. 이제 반대로 거리가 주어졌을 때 배열의 길이(시간)를 구하는 방법을 찾아야 합니다. 위에서 구한 대로 n²의 거리는 2n-1, n²+n의 거리는 2n에 도달이 가능합니다. 이미 앞에서 2n-1의 시간동안 갈 수 있는 거리가 n²임을 알았기 때문에 n²보다 크고 n²+n보다 작은 거리는 2n의 시간이 걸립니다. n²+n보다 크고 (n+1)²보다 작은 거리는 2n+1의 시간이 걸립니다. 주어진 거리 x에 대해 제곱근을 이용하여 앞의 두 비교를 하기 적합한 n을 찾은 뒤, 조건문을 통해 2n-1, 2n, 2n+1 중 올바른 시간을 선택하여 출력하면 됩니다.

소스 코드

언어	코드	시간
Python 3	코드(Github) / 코드(백준)	2020-03-26 23:06:47

---