언제나 처음처럼

[문제 링크]

문제에서 요구하는 조건대로 구현해주면 되는 문제였다.

입력으로 주어지는 정수의 최솟값이 -50 이므로, 음수까지 메모이제이션 하기 위해 값에 50을 더해줬다.

또한 a, b, c 셋 중에 하나라도 20을 넘는 값이 있을 경우 w(20, 20, 20)으로 재귀 호출 하기 때문에, memo 배열의 최대 크기를 101이 아닌 71로 선언하여 공간 복잡도를 줄였다.

#include <iostream>
using namespace std;

const int INF = 987654321;
int memo[71][71][71];

int dp(int a, int b, int c) {
	if (a <= 0 || b <= 0 || c <= 0) return 1;
	else if (a > 20 || b > 20 || c > 20) return dp(20, 20, 20);

	int& ret = memo[a+50][b+50][c+50];
	if (ret != 0)
		return ret;

	if (a < b && b < c)
		return ret = dp(a, b, c - 1) + dp(a, b - 1, c - 1) - dp(a, b - 1, c);
	else
		return ret = dp(a - 1, b, c) + dp(a - 1, b - 1, c) + dp(a - 1, b, c - 1) - dp(a - 1, b - 1, c - 1);
}

int main(void) {
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	while (true) {
		int a, b, c;
		cin >> a >> b >> c;

		if (a == -1 && b == -1 && c == -1)
			break;
		else {
			cout << "w(" << a << ", " << b << ", " << c << ") = " << dp(a,b,c) << '\n';
		}
	}

	return 0;
}

[문제 링크]

M이 100,000으로 매우 크기 때문에 행을 입력 받을 때 미리 각 행의 누적합을 구해놓고 이를 참조하는 방식으로 구현하였다.

(2,2) ~ (3,4) 의 구간합을 구해보자면,

(2,2) ~ (2,4) 까지의 합 + (3,2) ~ (3,4) 까지의 합이 된다.

(2,2) ~ (2,4) 까지의 합은 미리 구해놨던 (2,1) ~ (2,4) 까지의 누적합에 (2,1) ~ (2,1) 까지의 누적합을 빼준 것과 같다는 것을 알 수 있다.

(3,2) ~ (3,4) 까지의 합도 마찬가지로 (3,1) ~ (3,4) 까지의 누적합에 (3,1) ~ (3,1) 까지의 누적합을 빼준 것과 같다.

#include <iostream>
using namespace std;

int memo[1025][1025];

int sum(int y1, int x1, int y2, int x2) {
	int result = 0;
	for (int y = y1; y <= y2; y++) {
		if (x1 == 1)
			result += memo[y][x2];
		else
			result += memo[y][x2] - memo[y][x1-1];
	}

	return result;
}

int main(void) {
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	int N, M;
	cin >> N >> M;

	for (int y = 1; y <= N; y++) {
		for (int x = 1; x <= N; x++) {
			int num;
			cin >> num;

			if (x == 1)
				memo[y][x] = num;
			else
				memo[y][x] = memo[y][x - 1] + num;
		}
	}

	for (int i = 0; i < M; i++) {
		int x1, y1, x2, y2;
		cin >> y1 >> x1 >> y2 >> x2;

		cout << sum(y1, x1, y2, x2) << '\n';
	}

	return 0;
}

[문제 링크]

간단한 DP 문제였다.

상근이가 N킬로그램을 배달하는 봉지의 최소 갯수를 점화식으로 표현하면 다음과 같다.

result = 1 + min(dp(N-3), dp(N-5))

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

const int INF = 987654321;
int memo[5001];

int dp(int N) {
	if (N == 0) return 0;
	else if (N < 0) return INF;

	int& ret = memo[N];
	if (ret != -1)
		return ret;
	ret = INF;

	return ret = min(ret, 1 + min(dp(N - 3), dp(N - 5)));
}

int main(void) {
	memset(memo, -1, sizeof(memo));

	int N;
	cin >> N;
	
	int result = dp(N);
	cout << (result == INF ? -1 : result) << endl;

	return 0;
}

[문제 링크]

스택과 재귀를 이용하는 구현 문제였다.

문자열을 탐색하면서 숫자를 만날 경우 스택에 쌓아두고 '(' 를 만날 경우 그 다음 인덱스부터 재귀호출 하여 반환된 값에 스택의 가장 위에 있는 숫자를 곱해주는 방식으로 구현하였다.

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int decompress(string& str, int& here) {
	stack<char> stk;

	int ret = 0;

	while (str.size() > here) {
		if (str[here] == '(') {
			ret += (stk.top() - '0') * decompress(str, ++here);
			stk.pop();
		}
		else if (str[here] == ')') {
			here++;
			break;
		}
		else 
			stk.push(str[here++]);
	}
	ret += stk.size();

	return ret;
}

int main(void) {

	string str;
	cin >> str;

	int start = 0;
	cout << decompress(str, start) << endl;

	return 0;
}

[문제 링크]

은근히 까다로운 구현 문제였다.

2차원 세계 바깥쪽은 블록이 없기 때문에 빗물이 고이지 않는다. 따라서 첫번째와 마지막 블록의 높이가 중요하다고 볼 수 있다. 

필자는 주어진 배열에서 블록의 높이가 가장 높은 인덱스를 찾은 다음, 양 끝을 시작점으로 하여 두개의 포인터가 높이가 가장 높은 인덱스를 향해 가도록 구현하였다.

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

int H, W;
int block[501];

int getHighestIndex() {
	int highest = block[0];
	int idx = 0;

	for(int i=1; i<W; i++)
		if (highest <= block[i]) {
			highest = block[i];
			idx = i;
		}

	return idx;
}

int getRainWater() {
	queue<int> qFront, qBack;
	int highIdx = getHighestIndex();
	int frontHigh = 0, backHigh = 0;
	int ret = 0;

	for (int i = 0; i < W; i++) {
		int front = i;
		int back = W - 1 - i;

		if (front <= highIdx) {
			if (frontHigh > block[front]) {
				qFront.push(block[front]);
			}
			else {
				while (!qFront.empty()) {
					ret += frontHigh - qFront.front();
					qFront.pop();
				}
				frontHigh = block[front];
			}
		}

		if (back >= highIdx) {
			if (backHigh > block[back]) {
				qBack.push(block[back]);
			}
			else {
				while (!qBack.empty()) {
					ret += backHigh - qBack.front();
					qBack.pop();
				}
				backHigh = block[back];
			}
		}
	}

	return ret;
}

int main(void) {
	cin >> H >> W;

	for (int i = 0; i < W; i++)
		cin >> block[i];

	cout << getRainWater() << endl;

	return 0;
}

[문제 링크]

완전탐색 문제였다.

리모컨 버튼이 0~9 번까지 있기 때문에 버튼만 가지고 만들 수 있는 채널의 범위는 0~999999 이라는 것을 알 수 있다.

i = 0 부터 999999까지 숫자에 대해 고장나지 않은 버튼으로 만들 수 있는 숫자인지 확인하고 만들 수 있는 숫자라면 해당 채널로 이동할 경우 버튼 누르는 횟수를 계산해서 최솟값을 구하면 된다.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;

bool number[10];

bool isMakeNumber(int num) {
	string numStr = to_string(num);

	while (!numStr.empty()) {
		if (number[numStr.back() - '0'])
			numStr.pop_back();
		else
			return false;
	}

	return true;
}

int getMinimumClick(int N) {
	int start = 100;
	int ret = abs(N - start);

	for (int i = 0; i <= 999999; i++) {
		if (i == 100) continue;
		if (isMakeNumber(i)) {
			int click = to_string(i).size() + abs(N - i);
			ret = min(ret, click);
		}
	}

	return ret;
}

int main(void) {
	memset(number, true, sizeof(number));

	int N;
	cin >> N;

	int M;
	cin >> M;

	for (int i = 0; i < M; i++) {
		int num;
		cin >> num;
		number[num] = false;
	}

	cout << getMinimumClick(N) << endl;

	return 0;
}

[문제 링크]

LIS를 구하는 문제였다. 다만 수열의 길이가 1,000,000 으로 매우 길기 때문에 이중 for문을 돌려서 답을 얻는 일반적인 방법으로 구현할 경우 시간복잡도가 매우 커지게 된다.

따라서 다른 방법으로 구현해야 하는데... 예를 들어 다음과 같은 수열이 있다고 하자.

1  2  3  3  1  4  6  5

방법은 다음과 같다.

우선 첫 번째 인덱스에 있는 원소는 바로 추가한다.

1

그 다음 인덱스를 확인하여 LIS의 마지막 원소와 비교한다.

다음 인덱스의 원소는 2, LIS의 마지막 원소는 1 이다.

다음 인덱스의 원소가 더 클 경우 LIS의 맨 끝에 원소를 추가한다.

1  2

그 다음 인덱스를 확인하여 LIS의 마지막 원소와 비교한다.

다음 인덱스의 원소가 3이므로 2보다 크기 때문에 LIS의 맨 끝에 원소를 추가한다.

1  2  3

그 다음 인덱스를 확인하여 LIS의 마지막 원소와 비교한다.

다음 인덱스의 원소는 3, LIS의 마지막 원소 또한 3으로 같다.

다음 인덱스의 원소가 같거나 더 작을 경우 LIS 배열에서 정렬이 깨지지 않는 위치에 값을 덮어씌운다.

이때 LIS 배열은 오름차순으로 정렬되어 있는 상태이므로 이분 탐색을 통해 값을 바꿀 위치를 O(logN) 시간만에 찾을 수 있다.

1  2  3

이런 방식으로 배열의 모든 원소를 탐색하면 된다.

다음 인덱스의 원소는 1, LIS의 마지막 원소는 3 이다. 따라서 LIS 배열에서 값을 바꿀 위치를 찾는다.

1  2  3

다음 인덱스의 원소는 4, 마지막 원소는 3 이다. 따라서 LIS 배열 맨 끝에 4를 추가한다.

1  2  3  4

다음 인덱스의 원소는 6, 마지막 원소는 4 이다.

1  2  3  4  6

다음 인덱스의 원소는 5, 마지막 원소는 6이다.

1  2  3  5  6

LIS 배열의 원소는 총 5개. 따라서 LIS 의 길이는 5임을 알 수 있다.

이 방식으로 구현하게 되면 LIS가 어떻게 이루어져 있는지는 알 수 없지만, LIS 길이를 구하는데 있어서는

크기가 N인 배열의 모든 원소에 대하여 이분탐색을 수행하는 최악의 경우에도 O(NlogN)의 시간복잡도를 보장해준다.

#include <iostream>
using namespace std;

int N;
int arr[1000001];
int LIS[1000001];

int binary_search(int start, int end, int num) {
	int ret;

	while (start <= end) {
		int mid = (start + end) / 2;
		if (LIS[mid] >= num) {
			ret = mid;
			end = mid - 1;
		}
		else
			start = mid + 1;
	}

	return ret;
}

int getLIS() {
	int length = 1;
	
	LIS[0] = arr[0];
	for (int i = 1; i < N; i++) {
		if (LIS[length - 1] < arr[i]) {
			LIS[length] = arr[i];
			length++;
		}
		else {
			int idx = binary_search(0, length - 1, arr[i]);
			LIS[idx] = arr[i];
		}
	}

	return length;
}

int main(void) {
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	cout << getLIS() << endl;

	return 0;
}

[문제 링크]

그래프 탐색과 이분 탐색을 활용하는 문제였다.

공장이 있는 두 섬 A, B가 있다고 할 때, 중량을 견딜 수 있는 다리만 이용하여 A와 B를 왕래할 수 있는지 체크하기 위해 bfs를 이용하였다.

최대 중량을 구하기 위해 여러번의 bfs 탐색을 수행해야 하는데, 중량 C의 최대값이 10억으로 매우 크기 때문에 1~10억까지 전부 시도해보는 것이 아닌 이분 탐색을 활용하여 탐색 횟수를 최소화하였다.

추가로 섬의 개수 N이 최대 10000이므로, 그래프를 인접 행렬로 구현하게 되면 공간복잡도가 매우 커질 것이기에 인접리스트로 구현하여 공간복잡도를 줄였다.

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

int N, M;
vector<pair<int, int>> adj[10001];
bool visited[10001];

bool dfs(int start, int end, int weight) {
	if (start == end) return true;
	visited[start] = true;

	for (auto x : adj[start]) {
		int next = x.first;
		int bridge = x.second;

		if (bridge >= weight && !visited[next]) {
			if (dfs(next, end, weight))
				return true;
		}
	}

	return false;
}

bool bfs(int start, int end, int weight) {
	queue<int> q;
	q.push(start);
	visited[start] = true;

	while (!q.empty()) {
		int here = q.front();
		q.pop();

		if (here == end)
			return true;

		for (auto x : adj[here]) {
			int next = x.first;
			int bridge = x.second;

			if (bridge >= weight && !visited[next]) {
				q.push(next);
				visited[next] = true;
			}
		}
	}

	return false;
}

int getMaximumWeight(int factory1, int factory2) {
	int start = 1;
	int end = 1000000000;

	int ret = 0;

	while (start <= end) {
		memset(visited, false, sizeof(visited));

		int mid = (start + end) / 2;

		if (bfs(factory1, factory2, mid)) {
			start = mid + 1;
			ret = mid;
		}
		else
			end = mid - 1;
	}

	return ret;
}

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

	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int A, B, C;
		cin >> A >> B >> C;
		adj[A].push_back({ B,C });
		adj[B].push_back({ A, C });
	}

	int factory1, factory2;
	cin >> factory1 >> factory2;

	cout << getMaximumWeight(factory1, factory2) << endl;

	return 0;
}