문제접근
놓쳤던 부분
•
거꾸로 가는 걸 생각하면 됨
◦
#include <iostream>
#include <vector>
using namespace std;
int want;
int answer;
vector<bool> visited;
int main(void) {
int n, q;
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
visited.resize(n + 1);
for (int i = 0; i < q; i++) {
cin >> want;
int tmp = want;
while (true) {
if (tmp == 1) {
visited[want] = true;
cout << "0\n";
break ;
}
if (visited[tmp]) {
cout << tmp << "\n";
break ; //가장 작은 번호를 찾아야 하기 때문에 탈출을 하면 안 되고 끝까지 찾아봐야함
}
tmp /= 2;
}
}
return (0);
}
C++
복사
코드
2228 KB
48 ms
#include <iostream>
#include <vector>
using namespace std;
int want;
int answer;
vector<bool> visited;
int main(void) {
int n, q;
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
visited.resize(n + 1);
for (int i = 0; i < q; i++) {
cin >> want;
int tmp = want;
int answer = 0;
while (tmp > 1) {
if (visited[tmp])
answer = tmp;
tmp /= 2;
}
if (answer == 0)
visited[want] = true;
cout << answer << "\n";
}
return (0);
}
C++
복사
