C++[백준]12025번 장난꾸러기 영훈

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

12025번: 장난꾸러기 영훈

 

솔루션

---

처음에 완전 탐색으로 풀다가.. 메모리 초과를 받아서 알고리즘 분류를 보고 힌트를 얻었다.

 

이 문제 접근 하는 법을 몰랐더라면 꽤나 애 먹었을 문제이다.

 

 

문자열을 입력을 받은 후,

나는 역순으로 탐색을 했다.(순방향도 가능)

어느 한 인덱스의 값이 1,2,6,7 중 하나라면, 비트 연산자 &를 써서, k와 연산을 했을 때 참인지 거짓인지 확인을 한다.

 

참이라면, 해당 인덱스는 바뀌어야 하므로, 6,7중 하나를 넣고,

거짓이라면, 해당 인덱스는 바뀌지 않아야 하므로 1,2 중 하나를 넣는다.

 

 

그리고, k에서 해당 비트 값을 빼 준다.

 

그렇게 모든 문자열에 대해서 탐색하여 출력을 해 주면 정답이 된다.

 

만약 k가 0이 되지 않았다면, 바뀌어야 할 값이 더 남아있다는 뜻이므로 -1를 출력해주어야 한다. (이것 때문에 틀..)

 

 

코드

---

#define ll long long int
#include <iostream>
using namespace std;

string str;
string ans;
ll num;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> str;
	cin >> num;
	num--;
	ll bit = 1;
	for (int i = str.size() - 1; i >= 0; i--) {
		if (str[i] == '1' || str[i] == '6' || str[i] == '7' || str[i] == '2') {
			if (bit & num) {
				if (str[i] == '1' || str[i] == '6') {
					ans.push_back('6');
				}
				else {
					ans.push_back('7');
				}
				num -= bit;
			}
			else {
				if (str[i] == '1' || str[i] == '6') {
					ans.push_back('1');
				}
				else {
					ans.push_back('2');
				}
			}
			bit <<= 1;
		}
		else {
			ans.push_back(str[i]);
		}
	}

	if (num == 0) {
		for (int i = ans.size() - 1; i >= 0; i--) {
			cout << ans[i];
		}
		cout << "\n";
	}
	else cout << -1 << '\n';
}