백준 8741번 이진수 합

문제 입력값의 크기가 큰 것을 보고 눈치채야 했었다.

처음 짠 코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<int> deciTobi(long long num) {
	vector<int> reverse_result;
	vector<int> result;
	while (num > 0) {
		reverse_result.push_back(num % 2);
		num /= 2;
	}
	for (long long i = reverse_result.size()-1; i >= 0 ; i--) {
		result.push_back(reverse_result[i]);
	}
	return result;
}

int main() {
	long long k, sumresult = 0;
	cin >> k;
	long long end = pow(2, k);
	for (int i = 1; i < end; i++) {
		sumresult += i;
	}
	vector<int> result = deciTobi(sumresult);

	for (int i = 0; i < result.size(); i++) {
		cout << result[i];
	}
}

자신있게 풀었고 제출했더니 틀렸단다.

왜지? 하고 계속 쳐다봤는데 숫자 100을 입력하니 메모리 초과가 뜬다.

그때 깨달았다.

이건 10진수를 2진수로 바꾸는 문제가 아닌 것이라는 걸....

기왕 만든 코드로 1부터 10까지 돌려봤다.

규칙성이 나왔다.

k = 1 -> 1

k= 2 -> 110

k=3 -> 11100

k=4 -> 1111000

k=5 -> 111110000

규칙성이 보이는가?

 

답은 아래와 같다.

#include <iostream>

using namespace std;


int main() {
	int k;
	cin >> k;
	for (int i = 0; i < k; i++) {
		cout << 1;
	}
	for (int i = 0; i < k - 1; i++) {
		cout << 0;
	}
	cin >> k;
	return 0;
}

규칙성 찾기 문제였다.

다음에는 꼭 손으로 풀어보고 코딩해야겠다...