백준 12025 장난꾸러기 영훈

BOJ 12025

목표 : 영훈이는 장난꾸러기라서 희현이의 비밀번호 중 1은 6으로, 6은 1로 바꾸거나 2는 7으로 7은 2로 바꿔버렸다. 이를 해결하기 위해 희현이는 비밀번호 수열의 숫자 중 1과 6을 모두 1로, 2와 7을 모두 2으로 바꾼 숫자와 1과 6을 모두 6으로 2과 7을 모두 7로 바꾼 숫자 사이에 가능한 경우를 모두 사전순으로 나열한 다음 그 중 k번째 수열인 비밀번호를 찾기로 했다. 멘붕에 빠진 희현이의 비밀번호를 찾아주자.
조건 : K <= 2^63-1 0 <= 비밀번호의 자리수 <= 60

해결방안

#include <iostream>
#include <string>
#include <vector>
using namespace std;
string input;
long long N, M = 1;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> input >> N;
	for (int i = 0; i < input.length(); i++){
		if (input[i] == '1' || input[i] == '6'){
			input[i] = '1';
			M *= 2;
		}
		else if (input[i] == '2' || input[i] == '7'){
			input[i] = '2';
			M *= 2;
		}
	}	
	if (N > M || N < 0){
		cout << -1 << "\n";
	}
	else{
		N -= 1;
		for (int i = input.length()-1; i >= 0; i--){
			if (input[i] == '1'){
				if (N % 2) {
					input[i] = '6';
				}
				N /= 2;
			}
			else if (input[i] == '2'){
				if (N % 2) {
					input[i] = '7';
				}
				N /= 2;
			}
		}
		cout << input << "\n";
	}
	
	return 0;
}

k번째 비밀번호를 찾기위해서 가능한 비밀번호의 수열의 경우의 수는 1,2,6,7의 개수를 N개라고 할 때 2^N개이다. 이는 K를 2진수로 표현해 쉽게 해결할 수 있다. 예를 들어 K = 4이면 경우의 수는 0000~1111 까지 이고 0부터 시작하므로 0011번이 4번째 비밀번호임을 알 수 있고 2,3번째 문자만 6 또는 7로 변경해 해결할 수 있다.