20364번: 부동산 다툼

문제접근🤔

놓쳤던 부분😅

• 거꾸로 가는 걸 생각하면 됨

  #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);
  }
  

코드😁

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);
}