2164 카드2

문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.

출력

첫째 줄에 남게 되는 카드의 번호를 출력한다.

====

문제 풀이

시뮬레이션 코드라고 생각하여 배열을 만든 뒤 shift 와 push를 사용하였는데 시간초과가 발생.

규칙이 없을까 하고 shift와 push를 사용한 코드에 n이 1부터 100까지 넣어봤더니 2의 x승을 기준으로 그보다 작은 수들은 n이 1씩 작을 때마다 -2가 됨. 그래서 128까지 구해봤더니 역시나 2의 x승 기준으로 -2가 되었다. 

1 1
2 2
3 2
4 4
5 2
6 4
7 6
8 8
9 2
10 4
11 6
12 8
13 10
14 12
15 14
16 16
17 2
18 4
19 6
20 8
21 10
22 12
23 14
24 16
25 18
26 20
27 22
28 24
29 26
30 28
31 30
32 32
33 2
34 4
35 6
36 8
37 10
38 12
39 14
40 16
41 18
42 20
43 22
44 24
45 26
46 28
47 30
48 32
49 34
50 36
51 38
52 40
53 42
54 44
55 46
56 48
57 50
58 52
59 54
60 56
61 58
62 60
63 62
64 64
65 2
66 4
67 6
68 8
69 10
70 12
71 14
72 16
73 18
74 20
75 22
76 24
77 26
78 28
79 30
80 32
81 34
82 36
83 38
84 40
85 42
86 44
87 46
88 48
89 50
90 52
91 54
92 56
93 58
94 60
95 62
96 64
97 66
98 68
99 70
100 72
101 74
102 76
103 78
104 80
105 82
106 84
107 86
108 88
109 90
110 92
111 94
112 96
113 98
114 100
115 102
116 104
117 106
118 108
119 110
120 112
121 114
122 116
123 118
124 120
125 122
126 124
127 126
128 128

이것을 활용하여 n이상의 가장 가까운 2의 제곱수를 구한 뒤 그 제곱수로부터 n까지의 차이에 *2를 한 값에 제곱수를 빼주니 정답이 됨.

정답 코드

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const n = +input[0];
if (n === 1) {
    console.log(1);
    process.exit(0);
}

let i = 1;
while (Math.pow(2, i) < n) {
    i++;
}
const end = Math.pow(2, i);

console.log(end - (end - n) * 2);