굳건하게

문제 : 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;
}

[ 알고리즘풀이 ]

time[i] : i번 째 기능이 완성되는데 걸리는 시간.

--> time[i] = ((100 - progresses[i]) / speeds[i] ) + 1; // (100 - progresses[i]) % speeds[i] 가 0이 아니라면.
     time[i] = (100 - progresses[i]) / speeds[i];  // (100 - progresses[i]) % speeds[i] 가 0이라면.

 각각 기능별로 필요한 시간을 구하고, 앞에서부터 순회하며 한 번에 처리할 수 있는 최대 작업량을 count 한다. 현재 기준이 되는 time[i] 보다 작거나 같은 값들은 한 번에 처리할 수 있으므로 while 문을 통해 count 해주고, answer에 push 해준다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    int time[100]={};
    for(int i = 0; i < progresses.size(); i++){
        if((100 - progresses[i]) % speeds[i])
            time[i] = ((100 - progresses[i]) / speeds[i] ) + 1;
        else
            time[i] = (100 - progresses[i]) / speeds[i];
    }
    vector<int> answer;
    int i = 0, count = 0, s = time[0];
    while(i < progresses.size()){
        while(i < progresses.size() && s >= time[i]){
            count++;
            i++;
        }
        answer.push_back(count);
        if(i < progresses.size()){
            count = 0;
            s = time[i];
        }
    }   
    return answer;
}