백준 2812(크게 만들기)

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

2812번: 크게 만들기

 

간단하다.

 

N자리의 수가 주어졌을 때에 K개의 숫자를 지워서 가장 큰 수를 만드는 것이다.

 

그렇다면 큰 수의 조건은 무엇일까? 

 

A와 B를 비교하려면 어떻게 비교하는지에 대해서 생각해보자

 

먼저 최고자릿수를 비교한다. 수의 규모자체가 더 큰 게 더 큰 수가 되고, 같다면 그 최고자릿수의 크기에 따라서, 같다면 그 다음 자릿수에 따라서 수의 크기가 결정된다.

 

따라서 우리가 큰 수를 만드려면 최고자릿수가 가장 중요하단 것을 알 수 있다. 

 

따라서 가장 최고자릿수부터 조사하는 코드를 구현하도록 생각한다. 

 

만약에 앞에 자릿수의 수가 그 다음자릿수보다 작더라면 그 수를 먼저 없애는 것이 중요하다. 

 

3464

가 있고 하나를 없애면 

 

464 

 

두 개를 없애면 

 

64 

 

세 개를 없애면 

 

6이 된다. 

 

이 특징을 잘 이용해서 만약에 전보다 더 큰 수를 만나면, 그 전에 그 수보다 작은 수들을 지워나가는 방식으로 코드를 구현했다. 

 

#include<iostream>
using namespace std;
#define MAX 500050

int N, K;
int arr[MAX];
bool check[MAX];

int main() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		scanf_s("%1d", &arr[i]);
	}
	int idx = 0, num = K, big_idx=0;
	while (1) {
		if (idx == N - 1) break;
		if (arr[idx] < arr[idx + 1]) {
			big_idx = idx + 1;
			while (arr[idx] < arr[big_idx]) {
				if (num == 0) break;
				if (!check[idx]) {
					check[idx] = true;
					num--;
				}
				idx--;
				if (idx < 0) break;
			}
			if (num == 0) break;
			idx = big_idx;
		}
		else
			idx++;
	}

	int cnt = 0;
	for (int i = 0; i < N; i++) {
		if (cnt == N - K) break;
		if (check[i]) {
			continue;
		}
		cout << arr[i];
		cnt++;
	}
}

 

이번 코드를 짜면서 주의해야 할 점에 대해서 다시 생각해보았다. 

 

반복문이 겹칠때에 break를 쓴다면 그 break가 어디까지 빠져나가길 원하는지 잘 생각하고, 코드를 구현해야 한다. 

 

그리고 문제의 핵심이 뭔지 뭘 원하는 건지 잘 생각해보자 

 

코드를 무턱대고 짜는 것보다 코드를 어떤식으로 구현할지 생각하는게 중요하다