Mohand's code block

링크

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

해설

가방에 하나씩밖에 못 넣고 여러 개의 가방이 있으므로 각 가방에 넣을 수 있는 최대의 value 를 넣으면

최적화가 되므로 그리디 하게 넣으면 됩니다.

1. 보석과 가방을 모두 오름차순으로 정렬해두고 priority_queue(max heap) 를 준비합니다.

2. 가방에 대해 loop 를 만들고 각 가방 차례마다 넣을 수 있는 가장 큰 보석까지 priority_queue 에 넣습니다.

3. 이때 priority_queue 에는 보석의 가치만 넣으면 되므로 가치값만 넣습니다.

4. 그러면 priority_queue 의 top에는 현재 가방에 넣을 수 있는 가장 높은 가치가 있게 됩니다.

    물론 가방에 넣을 수 있는 보석이 하나도 없을 수도 있으니 체크합니다.

5. 정답에 += 하고 pop 하는 작업을 가방 끝까지 합니다. 

아래 코드에 모두 구현되어있습니다.

코드

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

int N, K, BAG[300000];
long long ANS = 0;
pair <int, int> GEM[300000];
priority_queue <int> que;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N >> K;

	for (int i = 0; i < N; ++i)
		cin >> GEM[i].first >> GEM[i].second;
	
	for (int i = 0; i < K; ++i)
		cin >> BAG[i];

	sort(GEM, GEM + N);
	sort(BAG, BAG + K);

	int idx = 0;

	for (int i = 0; i < K; ++i) {
		while (idx < N && GEM[idx].first <= BAG[i]) {
			que.push(GEM[idx].second);
			++idx;
		}
		if (!que.empty()) {
			ANS += que.top();
			que.pop();
		}
	}

	cout << ANS;

	return 0;
}

링크

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

해설

4개의 배열을 2개로 만드는 작업을 해야 합니다.

1번 2번  ||  3번 4번

이때 오른쪽은 미리 합을 다 구해둔 후 2진 search 를 위해 정렬을 해둡니다.

다음 각 왼쪽에서 모든 경우의 수에 대해 loop 를 돌립니다.

이때 오른쪽은 이미 정렬이 되어있으므로 upper_bound lower_bound 를 이용하여 2진탐색을 합니다.

그 후 값의 합이 0이면 upp - low 한 값을 정답에 더해줍니다.

4가지 배열을 각 2개씩 나눠서 계산 횟수를 줄이는 게 주목적입니다.

코드

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

long long NUM = 0;
int TABLE[4][4000];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N;
	cin >> N;

	for (int i = 0; i < N; ++i) {
		cin >> TABLE[0][i] >> TABLE[1][i] >> TABLE[2][i] >> TABLE[3][i];
	}

	vector <int> v;

	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			v.push_back(TABLE[2][i] + TABLE[3][j]);

	sort(v.begin(), v.end());

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			int now = TABLE[0][i] + TABLE[1][j];
			int low = lower_bound(v.begin(), v.end(), -now) - v.begin();
			int upp = upper_bound(v.begin(), v.end(), -now) - v.begin();
			if (v[low] == -now) {
				NUM += upp - low;
			}
		}
	}

	cout << NUM;

	return 0;
}

링크

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

해설

사실 이 문제를 풀려면 priority queue 를 2개를 사용한다는 발상이 중요합니다.

왜냐면 우리는 가운데 숫자만 관심이 있지 그 외의 숫자는 별 관심이 없거든요.

왼쪽의 priority queue 는 top 이 가장 큰 수가 되게 (내림차순)

오른쪽의 priority queue 는 top 이 가장 작은 수가 되게 (오름차순)

으로 셋팅을 하고 오른쪽 큐를 기준으로 값을 넣고 빼면 됩니다.

이때 지켜야할 규칙이 있는데

1. 오른쪽 큐의 크기 >= 왼쪽 큐의 크기

2. 항상 오른쪽 큐와 왼쪽큐의 최대 크기 차이는 1

이 두가지를 지키면서 queue 에 push 하면 됩니다.

그러면 왼쪽에는 항상 중간값 보다 작은 값들이 들어가 있고

오른쪽에는 중간값보다 큰 값들이 들어가게 됩니다.

오른쪽 큐를 중심으로 잡았으므로

1. 크기가 같으면 짝수개이므로 왼쪽 top, 오른쪽 top 중 작은 것

2. 크기가 다르면 홀수개 이므로 오른쪽 top

이 정답이 됩니다.

아래의 코드에 모두 구현되어있습니다.

코드

#include <iostream>
#include <queue>
using namespace std;

priority_queue <int> left_que;
priority_queue <int, vector<int>, greater<int>> right_que;

int min(int _a, int _b) { return _a < _b ? _a : _b; }

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N, temp;
	cin >> N;
	cin >> temp;
	cout << temp << "\n";
	right_que.push(temp);

	for (int i = 1; i < N; ++i) {
		cin >> temp;

		if (left_que.size() == right_que.size()) {
			if (temp >= right_que.top()) {
				right_que.push(temp);
			}
			else {
				left_que.push(temp);
				right_que.push(left_que.top());
				left_que.pop();
			}
			cout << right_que.top() << "\n";
		}
		else {
			if (temp >= right_que.top()) {
				right_que.push(temp);
				left_que.push(right_que.top());
				right_que.pop();
			}
			else {
				left_que.push(temp);
			}
			cout << min(left_que.top(), right_que.top()) << "\n";
		}
		
	}

	return 0;
}

링크

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

해설

DFS를 이용하는 문제입니다.

그런데 너무 무지성 DFS를 이용하면 타임아웃이 뜹니다.

바로 DFS 와 DP 를 조금 섞어서 풀어야 합니다.

왜 DP가 가능하냐 하면 다른 DFS문제들과는 조금 다른 점이 있습니다.

다른 문제들은 A에서 B로 갔을 때 다시 B에서 A로 가버리지 못하게 항상 검사를 했고

B는 항상 A로 가지 않았습니다.

그러나 이문제는 A에서 B로 갔을 때 다시 B에서 A로 돌아갈 수 있다는 보장이 없습니다.

즉 돌아갈 수 있게 되면 무한대 정답 -1 이 되어버립니다.

이러한 차이로 인해 각자의 점은 각자의 최대 갈 수 있는 횟수가 정해집니다.

알고리즘을 정리하면 한 점 A의 갈 수 있는 최대 횟수는 (다음점들의 value 들 중 가장 높은 값) + 1 입니다.

간단한 예를 들어보자면 백준의 예제 2번 을 사용해 보겠습니다.

1 10

2H3HH4HHH5

위와 같이 테이블이 만들어집니다.

위의 테이블에서 9번째 칸에서 이동할 수 있는 곳은 없습니다.

고로 9번에서 출발할 경우 최대 이동 횟수는 1 입니다.

5번째 칸에서 이동 가능한 곳은 9번째 칸 밖에 없습니다.

아까 9번째 칸에서 이동가능한 최대 횟수는 1로 구해뒀으니 5번째 칸의 최대 횟수는 2가 됩니다.

2번째 칸에서 이동가능한 곳은 5번째 칸 밖에 없습니다.

역시 마찬가지로 최대 횟수는 3이 됩니다.

마찬가지로 0번째 칸에서 이동 가능한 곳은 2번째 칸 밖에 없습니다.

최대 횟수는 4가 됩니다.

이렇게 계산을 완료하면 0번째 칸에서 출발해서 최대 횟수 정답은 4가 됩니다.

현재 설명은 down-top 방식으로 되어 있지만 이것을 반대로 top-down 으로 적용시키면

A 에서 갈 수 있는 4방위에 미리 구해둔 값이 있으면 그걸 그대로 쓰고, 없으면 계산을 실시하면 됩니다.

그리고 루프를 찾는 방법은 간단합니다.

똑같은 모양의 bool 테이블을 만들어서 현재 간 곳을 계속 기록하다가 만약 지나간 곳에 도달했다면

해당 위치에서 무한루프를 돌 수 있다는 것이므로 -1 을 return 합니다.

아래 코드에 모두 구현되어있습니다.

코드

#include <iostream>
using namespace std;

int N, M, TABLE[50][50], VALUE[50][50];
bool MEMORY[50][50];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

int DFS(int _x, int _y) {
	if (TABLE[_y][_x] == 0) {
		return 0;
	}
	if (VALUE[_y][_x] != 0)
		return VALUE[_y][_x];
	if (MEMORY[_y][_x])
		return -1;
	MEMORY[_y][_x] = true;
	int best = 0;
	for (int i = 0; i < 4; ++i) {
		int nx = _x + dx[i] * TABLE[_y][_x];
		int ny = _y + dy[i] * TABLE[_y][_x];
		if (0 <= nx && nx < M && 0 <= ny && ny < N) {
			int value = DFS(nx, ny);
			if (value == -1)
				return -1;
			best = best > value ? best : value;

		}
	}

	MEMORY[_y][_x] = false;
	VALUE[_y][_x] = best + 1;
	return best + 1;
}

int main()
{
	scanf("%d %d", &N, &M);
	getchar();
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			char ch = getchar();
			TABLE[i][j] = ch == 'H' ? 0 : ch - '0';
		}
		getchar();
	}
	
	printf("%d", DFS(0, 0));

	return 0;
}

링크

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

해설

반드시 포함되는 anta tica 에 대한 예외처리를 안 하면 시간 초과가 납니다.

혹시 시관 초과가 나서 보러 오셨다면 위의 예외처리를 해보시고 그래도 안되면 보시기 바랍니다.

간단한 백트래킹 문제입니다.

다만 반드시 포함되는 a c i n t 이 다섯 글자에 대한 예외처리만 하고 백트래킹을 하면 됩니다.

해결방법은 다음과 같습니다.

1. a c i n t 가 반드시 포함되어야 하므로 K 가 5 미만이면 0개입니다.

2. 5 이상이면 체크리스트에 a c i n t 를 입력하고 배울 수 있는 개수도 5개 줄입니다.

3. 각 알파벳에 대해 백트래킹을 하면서 브루트포스 알고리즘을 적용시킵니다.

저는 시간을 조금이라도 더 줄이려고 비트 마스킹을 이용해서 풀었습니다.

코드에 대한 약간의 설명을 드리자면

MASK : 이제껏 배운 알파벳들의 위치만 0 입니다.

SELECT : 단어들 중 한 번이라도 나온 알파벳들만 1입니다. (즉 배울 필요가 없는 걸 걸러 내는 용도)

TABLE은 기본적으로 모두 0으로 초기화돼있고 각 단어별로 해당 알파벳을 배워야 할 경우 해당 자리만 1로 바뀝니다.

DFS를 실시하기 전에 a c i n t 을 먼저 다 배우고 실시하는 조건이므로 MASK 에 0 처리

그리고 SELECT 에 이미 배웠으므로 0으로 빼줍니다.

그 후 백트래킹을 더 이상 할 수 없다고 판단되면 ( 더 배울 수 있는 단어의 수가 0 이거나 알파벳 끝까지 다 배운 경우)

각 테이블의 단어들과 지금까지 배운 알파벳 (MASK) 를 and 연산 후 ! 하면 읽을 수 있는지 나옵니다.

코드

#include <iostream>
using namespace std;

int N, K, BEST = 0;
unsigned int MASK = -1, SELECT = 0;
unsigned int TABLE[50] = { 0, };

void DFS(int _num) {
	for (; _num < 26; ++_num) {
		if (SELECT & 1 << _num)
			break;
	}
	if (K == 0 || _num == 26) {
		int now = 0;
		for (int i = 0; i < N; ++i) {
			if (!(TABLE[i] & MASK)) {
				++now;
			}
		}
		BEST = BEST > now ? BEST : now;
		return;
	}
	--K;
	MASK &= ~(1 << _num);
	DFS(_num + 1);
	MASK |= 1 << _num;
	++K;
	DFS(_num + 1);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> K;

	for (int i = 0; i < N; ++i) {
		char inp[16];
		cin >> inp;
		int j = 0;
		while (inp[j]) {
			TABLE[i] |= 1 << inp[j] - 'a';
			++j;
		}
		SELECT |= TABLE[i];
	}

	if (K < 5) {
		cout << '0';
	}
	else {
		unsigned int temp = 532741;
		SELECT &= ~temp;
		MASK &= ~temp;
		K -= 5;
		DFS(0);
		cout << BEST;
	}
	return 0;
}

링크

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

해설

사실 이문제는 세그먼트 트리를 이용하거나 펜윅 트리를 이용하면 더욱 빠르게 구할 수 있습니다.

세그먼트 트리를 이용한 방법과 펜윅 트리를 이용한 방법 둘 다 나중에 올리겠습니다.

근데 제가 배우질 않아서 일단 full binary tree 를 이용해서 풀었습니다.

코드는 간단합니다.

입력수만큼 받고 2^n 까지 나머지를 0으로 채우고 full binary tree 로 만들면 됩니다.

그 후 각 노드들은 하위 2개노드의 합을 적어두고

만약 값이 바뀔경우 해당 노드와 상위 노드의 갑만 수정해주면 됩니다.

a ~ b 까지의 합을 구하는 방법은

1. 쪼개고 쪼개다가 최소 단위가 되었을 경우

2. 쪼개던 중 쪼개진 범위가 구해야 하는 범위 안에 다 들어갈 경우

위의 2가지 경우를 모두 더해주면 a ~ b 까지 합을 구할 수 있습니다.

코드

#include <iostream>
using namespace std;

int N, M, K, NUM = 1;
long long TABLE[2097152];

long long sum(int _l, int _r, int _a, int _b, int _num) {
	if ((_l == _a && _r == _b) || _a == _b)
		return TABLE[_num];
	
	int mid_left = (_a + _b - 1) / 2, list_num_left = _num * 2 + 1;

	if (_r <= mid_left)
		return sum(_l, _r, _a, mid_left, list_num_left);
	else if (mid_left < _l)
		return sum(_l, _r, mid_left + 1, _b, list_num_left + 1);
	else
		return sum(_l, mid_left, _a, mid_left, list_num_left) + 
		       sum(mid_left + 1, _r, mid_left + 1, _b, list_num_left + 1);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M >> K;

	int finish, start;
	while (NUM < N) NUM *= 2;
	start = NUM - 1;
	finish = start * 2;
	
	for (int i = start; i < start + N; ++i)
		cin >> TABLE[i];
	
	for (int i = start + N; i <= finish; ++i) {
		TABLE[i] = 0;
	}

	for (int i = start - 1; i >= 0; --i) {
		int num = i * 2 + 1;
		TABLE[i] = TABLE[num] + TABLE[num + 1];
	}

	for (int i = 0; i < M + K; ++i) {
		int first, second;
		cin >> first >> second;

		if (first == 1) {
			long long third;
			cin >> third;
			int number = start + second - 1;
			long long gap = third - TABLE[number];
			while (true) {
				TABLE[number] += gap;
				if (number == 0)
					break;
				number = (number - 1) / 2;
			}
		}
		else {
			int third;
			cin >> third;
			cout << sum(second, third, 1, NUM, 0) << "\n";
		}
	}

	return 0;
}

링크

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

해설

백트래킹을 이용한 간단한 문제입니다.

방법 자체를 생각하는 건 어렵지 않으나 코드를 어떻게 짤지를 고민하는 게 더 중요해 보입니다.

제가 짠 코드는 각 행, 열, 사각형 에 대한 bool 배열을 만들어두고 3개다 true 이면 넣고 다음으로 넘어가는 방식입니다.

그 후 TABLE 에서 0인 칸을 찾아서 1~9 까지 다 넣어보고 하나도 안되면 false 로 뒤로 돌아가고 가능하면 더 가봅니다.

81번째까지 다 검사했는데도 0이 없으면 완성된 것이므로 해결!

코드

#include <iostream>
using namespace std;

int TABLE[81];
bool Y[9][9], X[9][9], square[9][9];

bool sudoku(int _n) {
	for (int i = _n; i < 81; ++i) {
		if (TABLE[i] == 0) {
			int x = i % 9, y = i / 9;
			for (int j = 0; j < 9; ++j) {
				if (X[x][j] && Y[y][j] && square[(y / 3) * 3 + x / 3][j]) {
					TABLE[i] = j + 1;
					X[x][j] = Y[y][j] = square[(y / 3) * 3 + x / 3][j] = false;
					if (sudoku(i + 1))
						return true;
					X[x][j] = Y[y][j] = square[(y / 3) * 3 + x / 3][j] = true;
				}
			}
			TABLE[i] = 0;
			return false;
		}
	}
	return true;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	for (int i = 0; i < 9; ++i)
		for (int j = 0; j < 9; ++j)
			Y[i][j] = X[i][j] = square[i][j] = true;
	

	for (int i = 0; i < 9; ++i) {
		for (int j = 0; j < 9; ++j) {
			int inp;
			cin >> inp;
			TABLE[9 * i + j] = inp;
			if (inp != 0) {
				--inp;
				Y[i][inp] = false;
				X[j][inp] = false;
				square[(i / 3) * 3 + j / 3][inp] = false;
			}
		}
	}



	sudoku(0);

	for (int i = 0; i < 9; ++i) {
		for (int j = 0; j < 9; ++j) {
			cout << TABLE[i * 9 + j] << " ";
		}
		cout << "\n";
	}

	return 0;
}

링크

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

해설

배열 내에서 두 개의 포인터를 가지고 이동하면 되는 문제입니다.

연속된 합이 S 이상인 것들 중 가장 길이가 짧은 것이니 오른쪽 포인터를 움직이다가

S이상이 되면 길이 체크 후 다시 왼쪽 포인터를 움직여서 줄이면 됩니다.

1. 현재 부분합이 S이상 - 더이상 늘려봤자 의미가 없으므로 다시 줄여야 함

 길이 짧은 것으로 교체

 합에서 TABLE[left] 빼기

 left++

2. 현재 부분합이 S 미만 - S이상이 되도록 늘려야 함

 right++

 합에 TABLE[right] 더하기

이렇게 두 포인터를 이용해서 부분합이 S이상인 것들 중 최소 길이만 다 확인해주면 됩니다.

코드

#include <iostream>
using namespace std;

int N, S, TABLE[100000];

int min(int _a, int _b) {
	if (_a < _b)
		return _a;
	return _b;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> S;

	for (int i = 0; i < N; ++i)
		cin >> TABLE[i];
	
	int left = 0, right = 0, now = TABLE[0], ans = 100001;

	while (right != N) {
		if (now < S) {
			++right;
			now += TABLE[right];
		}
		else {
			ans = min(ans, right - left + 1);
			now -= TABLE[left];
			++left;
		}
	}

	cout << (ans == 100001 ? 0 : ans);

	return 0;
}