[백준/BOJ]2812번 크게만들기

문제는 아래에!

 

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

2812번: 크게 만들기

 

 

 

처음에 간단하고 쉽다고 생각한 문제.(하지만 아니었다....)

크게 만드는것니까 작은 숫자들 순으로 지우면 될것이라고 생각했다. 

그렇게 틀리고 나서 반례를 찾던 중 질문 검색 쪽에  반례와 테스트 케이스를 확인하고 처음 설계했던 알고리즘이

완전히 틀렸다는것을 알게되었다.  단순히 가장 작은 숫자 순으로 지우는 것이 아니라 최대한 큰수를 만들어야하기에 제일 작진 않지만 앞자리이기 때문에 선택하지 말아야하는 경우가 있는 것이다.

 

[예시]

6 2
391123
//output : 9123
//가장 작은 숫자부터 지우게 된다면 답은 3923이 나오지만 실제로 답은 9123이다.

6 2
436436
//output : 6436

7 3
7654321
//output : 7654

6 2
362514
//output : 6514

_출처 : https://www.acmicpc.net/board/view/37870

위의 tc를 보고 이게 쉬운 문제가 아니겠구나 라고 느껴졌지만... 이미 풀기로 마음먹었으니 풀어야지 하는 생각으로 열심히 고민하였다.

 

큰수를 만들어야하기에 큰숫자를 기준으로 생각하기로 하고, 

생각해낸 방법은 재귀를 이용하는것인데,(쭉 탐색을 해야해서,,,)

 

 

1. 0~N-1 의 전체 숫자 배열 중 가장 큰수의 위치를 찾는다.(같은 숫자가 있을시 엔 앞자리 숫자를 선택.)

   -> 해당 인덱스 = idx;

2. [idx+1,N-1]까지의 숫자들중 가장 큰 수의 위치를 찾아 idx를 update.

3. 찾을 수 있을 때까지 들어가다가(==재귀) [idx+1,N-1]범위에서 선택할 수 있는 숫자가 없을 경우, return 후 부모 함수에서 다시 탐색할수있을 때까지 탐색.

4. 선택된 숫자의 개수가 조건과 같아진다면 재귀탐색을 종료.

[예시]
6 2
391123  이라면

1.[0,5]범위중 가장 큰 숫자 선택=> 9 / picknum++ ,idx=1
2.[idx+1(==2),5]범위중 가장 큰 숫자 선택 => 3 / picknum++ ,idx=5
3.[idx+1,5]범위중 가장 큰 숫자 선택 => 선택할 숫자 없음. =>부모 함수로 리턴
4.[idx+1(==2),5]범위중 가장 큰 숫자 선택 => 2 / picknum++ ,idx=4
5.[idx+1,5]범위중 가장 큰 숫자 선택 => 선택할 숫자 없음.(3이 이미 선택되어 있으므로) =>부모 함수로 리턴
6.[idx+1(==2),5]범위중 가장 큰 숫자 선택 => 1 / picknum++ ,idx=2(같은 숫자면 앞자리수 선택)
7.선택된 숫자가 조건에 맞으므로 재귀함수 종료.

=>답 : 9123 이다.

이런 식의 흐름이다. 

해당 차례에서 제일 큰 숫자가 중복 되어 있는경우, 앞자리를 선택해야 해당 차례에서 가장 큰 숫자가 큰자리에 들어갈 수 있게된다.

 

범위중 가장큰 숫자이면서 앞자리인 수(인덱스가 작은 수)를 구하기 위해 세그먼트 트리를 이용하였고, 비교하는 함수를 만들어 큰 숫자를 찾았다.

(주의) 찾은 제일 큰숫자가 0일 수도 있다! ->이거 빼먹어서 한번 더 틀렸다ㅜ

 

 

<코드>

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<functional>
#include<queue>
#include<math.h>
#include<stack>
#include<string.h>
#include<cmath>
#include<map>
using namespace std;
pair<int, int>big(pair<int, int> a, pair<int, int> b) {
	if (a.first == b.first) {
		if (a.second < b.second)return a;
		else return b;
	}
	else {
		if (a.first > b.first) return a;
		else return b;
	}
}
vector<pair<int, int>>seg;
int h = 1;
void update(int idx, int val) {
	int i = idx;
	idx += h - 1;
	seg[idx].first = val;
	seg[idx].second = i;
	while (idx > 1) {
		idx /= 2;
		seg[idx] = big(seg[idx * 2], seg[idx * 2 + 1]);
	}
}

pair<int, int> query(int L,int R,int node,int nodeL,int nodeR) {
	if (L <= nodeL&&nodeR <= R)return seg[node];
	else if (nodeR<L || nodeL>R)return{ -2,500005 };
	int mid = (nodeL + nodeR) / 2;
	return big(query(L, R, node * 2, nodeL, mid), query(L, R, node * 2 + 1, mid + 1, nodeR));
}
int num[500005];
int pick = 0;
int limit = 0;
void find(int s, int e) {
	pair<int, int>p;
	do {
		p = query(s, e, 1, 1, h);
		if (p.first > -1) {
			pick++;
			num[p.second] = p.first;
			update(p.second, -1);
			if(pick<limit)find(p.second, e);
		}
	} while (p.first > -1&&pick<limit);
}

int main(void) {
	memset(num, -1, sizeof(num));
	int N, M;
	scanf("%d %d", &N, &M);
	limit = N - M;
	while (N > h)h <<= 1;
	seg.resize(h * 2);
	for (int i = 1; i <= N; i++) {
		int n;
		scanf("%1d", &n);
		update(i, n);
	}
	
	find(1, N);

	string re = "";
	for (int i = 1; i <=N;i++) {
		if (num[i] >= 0)re += to_string(num[i]);
	}
	
	cout << re<<"\n";
	return 0;
}

 

 

 

 

다른 사람들 코드보면 정마 간단한게 푼 사람도 많더라ㅜㅜ...나는 언제 저 경지까지 갈까ㅜㅜ