[백준] 2164번: 카드2

https://www.acmicpc.net/problem/2164

2164번: 카드2

처음에는 deque 자료구조를 이용해 직접 풀어야 하나 고민했으나, 최대 500,000이라는 요소가 있어서 메모리가 초과될 수 있을 것 같아서 조금 더 효율적인 방법을 고안하기 시작했다.

1부터 16까지 시도해본 결과 정답에 일정한 패턴이 보이기 시작했다.

1

2

2 4

2 4 6 8

2 4 6 8 10 12 14 16

...

 

이런 식으로 일정한 구간으로 2씩 증가하는 양상이었다.

해당 구간이 멈추는 경우는 n개의 요소를 가지고 마지막에 n이라는 숫자가 남는 경우였다.

그 결과 한 구간에는 1을 제외하고 2의 제곱씩 늘어났다는 점을 이용해서 n이라는 숫자가 속하는 구간을 파악한 뒤, 끝 숫자와의 거리를 구하면 원하는 결과를 알 수 있다.

 

#include <iostream>
#include <cmath>
using namespace std;
int main() {
	int n;
	cin >> n;
	int len = 0;
	while(1 << len < n) {
		len++;
	}

	int last_num = pow(2, len);
	cout << last_num - 2 * (last_num - n) << '\n';
}