boj-20954-택배기사민서
boj_20954_택배기사 민서
🙋♂️ 들어가며
이번 문제는 지수를 생각해야하는 수학문제다.
굉장히 어려웠다
🧩문제
민서는 택배 기사이다. 활기차게 월요일을 맞은 민서는 놀라 자빠질 수밖에 없었다. 코로나19 사태로 인하여 비대면 활동이 확산되면서 택배 물량이 급증하였기 때문이다. 민서에게 배정된 택배는 거의 무한개에 가까웠고 이대로라면 과로사를 피할 수 없을 것이다. 민서는 건강을 위하여 오늘까지만 열심히 일하고 내일부터는 택배 기사 대신 교수를 하기로 결심하였다.
민서가 사는 동네는 수직선으로 표현할 수 있으며, 민서는 수직선의 원점, 즉 수직선의 좌표 0에서 배달을 준비하고 있다. 각 택배에는 0번부터 차례대로 번호가 매겨져 있으며, 택배의 목적지는 수직선 위의 좌표로 표현할 수 있다. i번 택배의 목적지 Di는 다음과 같다.
$D_i=(-1)^i×2^{\left\lfloor\frac{i}{2}\right\rfloor}$
여기서 ⌊x⌋는 바닥 함수로, x보다 크지 않은, 즉 x 이하의 정수 중 가장 큰 정수를 의미한다. 예를 들어, 3번 택배의 목적지 D3은 다음과 같이 계산할 수 있다.
$D_3=(-1)^3×2^{\left\lfloor\frac{3}{2}\right\rfloor}=-2$
민서는 수직선의 원점에서 출발하여 0번 택배부터 차례대로 배달을 시작한다. 택배를 배달하기 위해서는 현재 위치로부터 택배의 목적지까지 이동해야 한다. 민서는 현재 좌표에서 인접한 좌표로, 즉 현재 좌표에서 1만큼 차이 나는 좌표로 이동할 수 있으며, 이때 1초의 시간이 소요된다. 또한 민서는 항상 최단 경로로 이동한다.
민서는 온종일 쉬지도 않고 열심히 택배를 배달하고 있다. 문득 민서는 수직선 위의 특정 좌표 x에 처음으로 도달하는 시점이 언제인지 궁금해졌다.
좌표 x가 주어졌을 때, 해당 좌표에 처음으로 도달하는 시점을 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
이후 T개의 줄에 걸쳐 정수 좌표 x가 한 줄에 하나씩 주어진다.
출력
각 테스트 케이스에 대한 답을 한 줄에 하나씩 출력한다.
제한
1 ≤ T ≤ 100,000
-1,000,000,000 ≤ x ≤ 1,000,000,000
예제 입력 1
1
2
3
4
5
6
5
0
1
2
3
4
예제 출력 1
1
2
3
4
5
0
1
6
15
16
힌트
입력과 출력의 양이 방대하므로 빠른 입출력을 사용할 것을 권장한다.
답이 32비트 정수 자료형의 표현 범위를 초과할 수 있음에 유의하라.
🤔내 사고의 흐름
0번부터 차례대로 시작
원점에서 출발하는데
1칸당 1초씩 +방향 or -방향으로 움직일 수 있다
우선 문제에 나오는 점화식 값을 구해보자
| $D_i$ | 값 |
|---|---|
| $D_0$ | 1 |
| $D_1$ | -1 |
| $D_2$ | 2 |
| $D_3$ | -2 |
| $D_4$ | 4 |
| $D_5$ | -4 |
| $D_6$ | 8 |
| $D_7$ | -8 |
순서가 아래와 같네
1
+ - + - + - ~~~ (이하 동일)
테스트케이스1 참고하자
+방향 or -방향
어디서부터 출발하지?
우선 순서가 위와 같으니 양의방향에 먼저 출발한다고 가정하겠다
time, x 표를 작성해보자
| t | x |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 0 |
| 3 | -1 |
| 4 | 0 |
| 5 | 1 |
| 6 | 2 |
| 7 | 1 |
| 8 | 0 |
| 9 | -1 |
| 10 | -2 |
| 11 | -1 |
| 12 | 0 |
| 13 | 1 |
| 14 | 2 |
| 15 | 3 |
| 16 | 4 |
| 17 | 3 |
| 18 | 2 |
| 19 | 1 |
| 20 | 0 |
| 21 | -1 |
| 22 | -2 |
| 23 | -3 |
| 24 | -4 |
| 25 | -3 |
| 26 | -2 |
| 27 | -1 |
| 28 | 0 |
나만의 test case를 -(음수)로 하나 더 만들어보자
+(양수)
1
2
3
4
5
0 -> 0
1 -> 1
2 -> 6
3 -> 15
4 -> 16
-(음수)
1
2
3
4
5
0 -> 0
-1 -> 3
-2 -> 10
-3 -> 23
-4 -> 24
원점인 0부터 중복되지 않는 범위까지 탐색하는데 $2^N$ 씩 증가한다.
어 양수인 경우에는
음수인 경우에는
아 이렇게 짜면 되겠다
x가 0보다 클 때
1
4 * ( (1L << k) -1 ) + x
x가 0보다 작을 때
1
4 * ( (1L << k) -1 ) + 2 * ( (1L << k) ) + abs_x
최종코드
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/*
D_0 ~ D_7 까지 구하면 +-+-+- 반복되는 것을 알 수 있다
그리고 테스트케이스를 검증해보면 원점에서 양수로 먼저 가는 것을 확인
*/
package boj;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
while (T-- > 0) {
long x = Long.parseLong(br.readLine());
if (x == 0) {
sb.append(0);
sb.append("\n");
continue;
}
long abs_x = Math.abs(x);
long k = 0;
while ( (1L << k) < abs_x ) {
k++;
}
long total_time = 0;
if (x > 0) {
total_time = 4 * ( (1L << k) -1 ) + x;
}
else if (x < 0) {
total_time = 4 * ( (1L << k) -1) + ( 2 * (1L << k) ) + abs_x;
}
sb.append(total_time).append("\n");
}
System.out.println(sb.toString());
}
}
