글 읽기 - 이 문제에서 k를 언제 사용할까요??

nlkey2022 6년 전 0

dp로 코딩했기 보다는..

뭔가 dp로 생각하긴 어려워 그냥 무식하게 풀어봤습니다.

reduce는 1 1 2 2 3 3 2 2 2 1 이런 수열을

1 2 3 2 1 와 같이 간단하게 하는 함수입니다.

아래 예제에서는 다음과 같습니다

1 1 2 3 3 3 2 2 1 1

1 2 3 2 1

여기서 3을 2로 바꿀때 (3을 제거하는) 수열이 가장 짧아지므로

1 2 2 2 1 count 1

1 2 1

여기서 2를 1로 바꿀때 (2를 제거하는) 수열이 가장 짧아지므로

1 1 1 count 2

K를 이 문제에서 어떻게, 언제 사용할까요?

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> reduce(vector<int> light) {
	vector<int> copy;
	vector<int>::iterator it;
	for (it = light.begin(); it != light.end(); it++) {
		if (it == light.end() - 1) {
			copy.push_back(*it);
		}
		else if (*it != *(it+1)) {
			copy.push_back(*it);
		}
	}
	return copy;
}

int main() {
	vector<int> light;
	int n; cin >> n;
	int k; cin >> k;

	for (int i = 0; i < n; i++) {
		int temp; cin >> temp;
		light.push_back(temp);
	}

	light = reduce(light);

	int count = 0;
	while (true) {
		vector<pair<int, int>> lenght;
		

		light = reduce(light);
		if (light.size() == 1) break;

		for (int i = 0; i < light.size(); i++) {
			vector<int> temp;
			
			// light temp call by value;
			for (int j = 0; j < light.size(); j++) {
				vector<int>::iterator iter = light.begin();
				advance(iter, j);
				temp.push_back(*iter);
			}

			vector<int>::iterator _it = temp.begin();
			advance(_it, i);
			temp.erase(_it);
			temp = reduce(temp);
			lenght.push_back(pair<int, int>(temp.size(), i));
		}
		// temp size에 의한 sort
		sort(lenght.begin(), lenght.end());

		vector<int>::iterator it = light.begin();
		advance(it, lenght.begin()->second);
		light.erase(it);

		count++;
	}
	cout << count;
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이 문제에서 k를 언제 사용할까요??

nlkey2022 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말