[BAEKJOON] 20310번 타노스

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

20310번: 타노스

 

문제조건

1. 0과 1로만 이루어진 문자열 S가 있음
2. 0과 1의 개수가 각각 짝수개임
3. 각각 절반의 개수를 제거했을때, 사전순으로 가장 빠른 문자열 구하기

1분만에,,? 풀었나,,? 이렇게 쉬운게 왜 정답률이 50%가 안되지 라고생각하며 풀었다.

#include <iostream>
#include <vector>
using namespace std;
//S가 포함하는 0과 1의 개수 모두 짝수
//절반 제거후 사전순으로 가장빠른 거 구하기
string s;
int main(){
	cin >> s;
	vector<int> res;
	int cnt0 = 0, cnt1 = 0;
	for(int i = 0; i < s.length(); i++) {
		if (s[i] == '0') cnt0++;
		else cnt1++;
	}
	for (int i = 1; i <= cnt0 / 2; i++) res.push_back(0);
	for (int i = 1; i <= cnt1 / 2; i++) res.push_back(1);
	for (int i : res) cout << i;
}

ㅎㅎ

진짜 잘못된게 없는 것 같은데 계속 생각해보니, 또 문제를 보고 뭔가 잘못되었음을 깨달았다.

문제에 주어진 조건은 0과 1을 절반씩 없애고 재배열해서 사전순으로 가장 앞에 오는 것을 출력하는것이 아닌! 없애기만 하고 남은 문자열이 사전순으로 가장 앞에 오는 경우가 어떤 경우인가를 물어 보는것이었다,,,

이번기회에 또 문제를 꼼꼼히 읽는 것에대해 중요함을 느꼈다.

 

#include <iostream>
#include <vector>
using namespace std;
//S가 포함하는 0과 1의 개수 모두 짝수
//절반 제거후 사전순으로 가장빠른 거 구하기
//순서를 바꿀수는 없음!!
string s;
bool check[501];
int main(){
	cin >> s;
	int cnt0 = 0, cnt1 = 0;
	for(int i = 0; i < s.length(); i++) {
		if (s[i] == '0') cnt0++;
		else cnt1++;
	}
	int zero = 0;
	for (int i = s.length(); i >= 0; i--) {
		if (cnt0/2 == zero) break;
		if (s[i] == '0') {
			zero++;
			check[i] = true;
		}
	}
	int one = 0;
	for (int i = 0; i < s.length(); i++) {
		if (cnt1/2 == one) break;
		if (s[i] == '1') {
			one++;
			check[i] = true;
		}
	}
	string res = "";
	for (int i = 0; i < s.length(); i++) {
		if (!check[i]) res += s[i];
	}
	cout << res;
}

 

사전순으로 가장 빠르게 오게 지우려면 어떻게 접근해야할까?

당연히 0이 앞에 오고 1이 뒤에 올수록좋으므로, 앞에서부터 접근해서 1을 최대한 지워주고, 뒤에부터 접근해서 0을 최대한 지워주면 된다. 바로 Greedy(탐욕법) 접근법이다.

 

부분해가 최적의 해가되는 마법(?)을 느꼈다.

편---안