굳건하게

문제 : https://www.acmicpc.net/problem/15665

[ 알고리즘풀이 ]

 입력값에서 중복을 제외하고 Backtracking 을 이용해 M개를 뽑으면 된다.

#include<iostream>
#include<vector>

using namespace std;

int N, M, x;
vector<int> input;
bool check[10001] = {};

void Backtracking(vector<int> v) {
	if (v.size() == M) {
		for (int i = 0; i < v.size(); i++)
			cout << v[i] << ' ';
		cout << '\n';
		return;
	}
	for(int i = 0; i < input.size(); i++){
		v.push_back(input[i]);
		Backtracking(v);
		v.pop_back();
	}
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> x;
		check[x] = 1;
	}

	for (int i = 0; i <= 10000; i++)
		if (check[i])
			input.push_back(i);

	vector<int> v;
	Backtracking(v);

	return 0;
}

문제 : https://www.acmicpc.net/problem/2096

[ 알고리즘풀이 ]

 이 문제는 전형적인 쉬운 2차원 DP 문제이나, 4MB 라는 메모리 제한 때문에 배열 선언에 제약이 걸려있는 문제입니다. 따라서, 2행 3열짜리 2차원 배열을 선언해서 첫 번째 행에는 현재까지 가장 큰 값, 가장 작은 값을 저장하고 두 번째 행에는 들어온 입력값과 첫 번째 행의 값을 이용해 새롭게 가장 큰 값, 가장 작은 값은 갱신해줍니다. 그 후, 두 번째 행을 첫 번째 행에 덮어가며 N행 3열 2차원 배열이 아닌 2행 3열 2차원 배열로 문제를 해결할 수 있습니다.

ansMap[0][j].first : 현재까지 j번 째 열에서 얻을 수 있는 가장 큰 값

ansMap[0][j].second : 현재까지 j번 째 열에서 얻을 수 있는 가장 작은 값

#include<iostream>
#include<algorithm>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int N, map[3] = {};
	pair<int, int> ansMap[2][3] = {};

	cin >> N;
	cin >> map[0] >> map[1] >> map[2];
	for (int j = 0; j < 3; j++) {
		ansMap[0][j].first = ansMap[0][j].second = map[j];
	}

	for (int i = 1; i < N; i++) {
		cin >> map[0] >> map[1] >> map[2];
		ansMap[1][0].first = max(ansMap[0][0].first, ansMap[0][1].first) + map[0];
		ansMap[1][0].second = min(ansMap[0][0].second, ansMap[0][1].second) + map[0];
		ansMap[1][1].first = max({ ansMap[0][0].first, ansMap[0][1].first, ansMap[0][2].first }) + map[1];
		ansMap[1][1].second = min({ ansMap[0][0].second, ansMap[0][1].second, ansMap[0][2].second }) + map[1];
		ansMap[1][2].first = max(ansMap[0][1].first, ansMap[0][2].first) + map[2];
		ansMap[1][2].second = min(ansMap[0][1].second, ansMap[0][2].second) + map[2];
		for (int j = 0; j < 3; j++)
			ansMap[0][j].first = ansMap[1][j].first, ansMap[0][j].second = ansMap[1][j].second;
	}
	cout << max({ ansMap[0][0].first, ansMap[0][1].first, ansMap[0][2].first }) << ' ' << min({ ansMap[0][0].second, ansMap[0][1].second, ansMap[0][2].second });
}

문제 : https://www.acmicpc.net/problem/11003

[ 알고리즘풀이 ]

 처음에는 세그트리를 이용하는 문제가 아닐까 고민하다가 Deque(덱)을 이용하면 된다는 것을 뒤늦게 캐치했다.

 Deque에는 < value, index > 를 저장하는데 Deque의 front 에는 현재 범위에서 가장 작은 값을 저장해 나갈 것이다.

1) 현재 가장 작은 값인 front 의 index가 범위 밖이라면 pop_front 를 진행한다.

2) 새로 들어온 값을 Deque의 back 부터 순회하며 새로 들어온 값보다 큰 값들은 새로 들어온 값에 의해 의미가 없어지므로 다 pop_back 을 진행한다. 

3) 새로 들어온 값을 push_back 해준다.

4) 2), 3)의 과정에 의해 Deque의 front 에는 범위 안에 있으면서 가장 작은 값이 오게된다. 따라서, Deque의 front 값을 출력해준다.

#include<iostream>
#include<deque>

using namespace std;

int N, L, x;
deque<pair<int, int>> list;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> L;
	for (int i = 0; i < N; i++) {
		cin >> x;
		if (!list.empty() && list.front().second <= (i - L))
			list.pop_front();

		while (!list.empty() && list.back().first >= x)
			list.pop_back();

		list.push_back({ x, i });
		cout << list.front().first << ' ';
	}

	return 0;
}

문제 : https://www.acmicpc.net/problem/8120

[ 알고리즘풀이 ]

 입력으로 들어온 값들을 역으로 순회하며 답을 채워나갈 것이다.

input[x] : x번 째 입력값

check[x] : 1 ~ N 중에서 x 값을 사용했는지 안 했는지 

 현재 input[x] 가 k 라면 아직 사용 안 한 값 중에서 (k + 1) 번째로 큰 값을 선택합니다. 그러면, 역순으로 채우고 있기 때문에 input[x] 보다 값이 크면서 index는 작은 값들이 k 개가 됩니다. 이때, 아직 사용 안 한 값 중에서 (k + 1)번 째로 큰 값이 없다면 불가능한 경우이므로 "NIE"를 출력합니다.

ex) input = [ 0 0 1 0 2 0 4 ] 

input 배열을 역으로 순회하며 정답 배열을 채워보자.

1) input[7] = 4 / check = [ 0 0 0 0 0 0 0 ]

check 배열을 순회하며 아직 사용 안 한 값 중에서 5번 째로 큰 값을 선택한다.

→ ans[7] = 3

2) input[6] = 0 / check = [ 0 0 1 0 0 0 0 ]

→ ans[6] = 7

3) input[5] = 2 / check = [ 0 0 1 0 0 0 1 ]

→ ans[5] = 4

4) input[4] = 0 / check = [ 0 0 1 1 0 0 1 ]

→ ans[4] = 6

5) input[3] = 1 / check = [ 0 0 1 1 0 1 1 ]

→ ans[3] = 2

6) input[2] = 0 / check = [ 0 1 1 1 0 1 1 ]

→ ans[2] = 5

7) input[1] = 0 / check = [ 0 1 1 1 1 1 1 ]

→ ans[1] = 1

#include<iostream>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int N, input[30001] = {}, ans[30001] = {};
	bool check[30001] = {};

	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> input[i];

	bool flag = false;
	for (int i = N; i >= 1; i--) {
		int c = 0, j = N;
		while (!(c == input[i] && !check[j])) {
			if (!check[j])
				c++;
			j--;
		}
		if (j < 1) {
			flag = true;
			break;
		}
		ans[i] = j;
		check[j] = 1;
	}

	if (flag)
		cout << "NIE\n";
	else{
		for (int i = 1; i <= N; i++)
			cout << ans[i] << '\n';
	}
}

세그트리를 이용해서 푸신 분들이 많은데, 코드를 뜯어보고 추후에 다시 포스팅하도록 하겠습니다.