언제나 처음처럼

[문제 링크]

간단한 그래프탐색 문제였다.

자신의 키가 정확히 몇번째인지 알기 위해선 다른 모든 학생들과 그래프가 연결되어 있어야 한다.

우선, 연결되어 있는 학생들을 체크하는 함수는 dfs로 구현하였다.

학생 a보다 학생 b의 키가 더 큰지 여부를 확인하기 위해선 adj[a][b] == true 인지 확인하면 되고,

학생 a보다 학생 b의 키가 더 작은지 여부를 확인하기 위해선 그 반대인 adj[b][a] == true 인지 확인하면 된다.

따라서 키가 더 큰 학생들을 체크하는 dfs, 키가 더 작은 학생들을 체크하는 dfs를 수행하여 모든 학생들과 연결되어 있는지 알 수 있도록 구현하였다.

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

int N, M;
bool adj[501][501];
bool visited[501];
const int DOWN = 1;
const int UP = 2;

int dfs(int here, int type) {
	int ret = 1;
	visited[here] = true;

	for (int i = 1; i <= N; i++) {
		if (type == DOWN) {
			if (adj[here][i] && !visited[i])
				ret += dfs(i, type);
		}
		else if (type == UP) {
			if (adj[i][here] && !visited[i])
				ret += dfs(i, type);
		}
	}

	return ret;
}

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

	cin >> N >> M;

	while (M--) {
		int a, b;
		cin >> a >> b;
		adj[a][b] = 1;
	}

	int result = 0;
	for (int i = 1; i <= N; i++) {
		memset(visited, false, sizeof(visited));
		int visitCnt = dfs(i, DOWN) + dfs(i, UP) - 1;
		if (visitCnt == N)
			result++;
	}

	cout << result << endl;

	return 0;
}

[문제 링크]

dp의 메모이제이션 기법을 이용하는 전형적인 피보나치 수열 문제였다.

다만, n의 최대가 10000인데, 피보나치 수열은 갈수록 값이 어마어마하게 커지기 때문에 n의 값이 클경우 unsigned long long 자료형에도 담을 수 없을 정도로 커지게 된다.

따라서 숫자를 문자열로 표현한 다음, 두 문자열의 합을 구해주는 sum 함수를 구현하여 이와 같은 문제를 해결하였다.

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

string memo[10001];

string sum(string a, string b) {
	string result;
	int up = 0;

	// 자리수가 다를 경우 뒤에 있는 수가 반드시 자리수가 큼
	while (!b.empty()) {
		if (!a.empty()) {
			int num1 = a.back() - '0';
			int num2 = b.back() - '0';
			a.pop_back();
			b.pop_back();

			int sum = num1 + num2 + up;
			up = 0;

			if (sum >= 10) {
				up = 1;
				sum -= 10;
			}
			result.push_back(sum + '0');
		}
		else {
			int num = b.back() - '0';
			b.pop_back();

			int sum = num + up;
			up = 0;

			if (sum >= 10) {
				up = 1;
				sum -= 10;
			}
			result.push_back(sum + '0');
		}
	}
	if (up == 1)
		result.push_back('1');

	reverse(result.begin(), result.end());

	return result;
}

string bottomUp(int n)
{
	memo[0] = '0', memo[1] = '1';
	
	for (int i = 2; i <= n; i++) {
		memo[i] = sum(memo[i - 2], memo[i - 1]);
	}
	
	return memo[n];
}

int main(void)
{
	int n;
	cin >> n;

	cout << bottomUp(n) << endl;
	
	return 0;
}

10000번째 피보나치 수열은 정말 어마어마한 숫자이다.....

[문제 링크]

간단한 bfs 문제였다.

문제에 주어진 3가지 방법을 각각 구현하여 이를 수행한 3가지 결과를 큐에 담아주도록 구현하였다.

방문 체크는 이모티콘의 개수 뿐만이 아니라 클립보드에 저장된 이모티콘의 개수에 따라서도 결과가 바뀔 수 있기 때문에 2차원 visited 배열을 선언하였다.

visited 배열 대신 memo 배열을 통해 메모이제이션 기법을 활용하여 풀이한 코드도 추가하였다.

// bfs

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

bool visited[2001][2001];

struct info {
	int cnt;
	int clipBoard;
	int time;
};

int bfs(int S) {
	int start = 1;
	queue<info> q;
	q.push({ start, 0, 0 });
	visited[start][0] = true;

	while (!q.empty()) {
		int cnt = q.front().cnt;
		int clipBoard = q.front().clipBoard;
		int time = q.front().time;
		q.pop();

		if (cnt == S)
			return time;

		// case 1
		if (!visited[cnt][cnt]) {
			q.push({ cnt, cnt, time + 1 });
			visited[cnt][cnt] = true;
		}

		// case 2
		if (cnt+clipBoard < 2000 && !visited[cnt + clipBoard][clipBoard]) {
			q.push({ cnt + clipBoard, clipBoard, time + 1 });
			visited[cnt + clipBoard][clipBoard] = true;
		}

		// case 3
		if (cnt - 1 > 0 && !visited[cnt - 1][clipBoard]) {
			q.push({ cnt - 1, clipBoard, time + 1 });
			visited[cnt - 1][clipBoard] = true;
		}
	}

	return -1;
}
int main(void) {
	int S;
	cin >> S;

	cout << bfs(S) << endl;

	return 0;
}

// dp

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

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

int dp(int here, int clipBoard, int S) {
	if (here < 0 || here > S*2 || clipBoard > S*2) return INF;
	if (here == S) return 0;

	int& ret = memo[here][clipBoard];
	if (ret != 0) return ret;
	ret = INF;

	int case1 = dp(here, here, S) + 1;
	int case2 = dp(here - 1, clipBoard, S) + 1;
	int case3 = dp(here + clipBoard, clipBoard, S) + 1;

	ret = min(ret, min(case1, min(case2, case3)));
	return ret;
}

int main(void) {
	int S;
	cin >> S;

	cout << dp(1, 0, S) << endl;

	return 0;
}

[문제 링크]

트라이 자료구조를 활용하는 문제였다.

우선 전화번호 목록을 트라이에 담으면서 전화번호의 끝자리인 노드를 체크하였다.

그다음, 완성된 트라이에서 전화번호를 검색하여 끝자리에 도달하기 전에 다른 전화번호의 끝자리인 노드에 방문하게 되는지 여부를 판단하여 입력받은 전화번호 목록이 일관성 있는 목록인지 아닌지를 알 수 있다.

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

const int NUMBER = 10;

class TrieNode {
	TrieNode* children[NUMBER];
	bool terminal;

public:
	TrieNode() : terminal(false) {
		memset(children, 0, sizeof(children));
	}
	~TrieNode() {
		for (int i = 0; i < NUMBER; i++)
			if (children[i] != 0) delete children[i];
	}

	void insert(string& key, int here) {
		if (here == key.size()) 
			terminal = true;
		else {
			int next = key[here] - '0';
			if (children[next] == NULL)
				children[next] = new TrieNode();

			children[next]->insert(key, here + 1);
		}
	}

	bool find(string& key, int here) {
		if (here == key.size()) return true;
		
		if (this->terminal)
			return false;

		int next = key[here] - '0';
		return children[next]->find(key, here + 1);
	}
};

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

	int t;
	cin >> t;
	
	while (t--) {
		int n;
		cin >> n;

		vector<string> numberList(10001);
		TrieNode* trie = new TrieNode();

		for (int i = 0; i < n; i++) {
			string num;
			cin >> num;
			numberList[i] = num;
			trie->insert(num, 0);
		}

		bool flag = true;
		for (int i = 0; i < n; i++) {
			if (!trie->find(numberList[i], 0)) {
				cout << "NO" << '\n';
				flag = false;
				break;
			}
		}
		if (flag)
			cout << "YES" << '\n';

		delete trie;
	}
}

[문제 링크]

재밌으면서도 골치아팠던 그래프 & 시뮬레이션 문제였다.

우선 궁수를 3명 배치하는 조합의 경우 3중 for문을 이용하여 간단하게 구현할 수 있다.

그 다음, 궁수가 공격할 대상을 정하는 것을 구현해야 하는데 조건은 다음과 같다.

1. 궁수는 동시에 공격한다. --> 같은 적을 여러명의 궁수가 공격하게 될 수 있다.

2. 사거리 내 적이 여러명 있는 경우 가장 가까이 있는 적을 공격한다.

3. 같은 사거리에 있는 적의 경우 가장 왼쪽에 있는 적을 공격한다.

여러명의 궁수가 같은 적을 공격하는 경우 킬포인트가 중복으로 누적되는 것을 방지하기 위해 이미 죽은 적은 '2'로 마킹하여 공격은 하되, 킬포인트는 올라가지 않도록 구현하였다.

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

int N, M, D;
int board[15][15];

class Archer {
private:
	int y;
	int x;
	int distance;
	int kill;
public:
	Archer(int _x) : y(N), distance(D), kill(0) {
		x = _x;
	}

	void searchEnemy() {
		for (int d = 1; d <= distance; d++) {
			int i = 1;
			while (i <= d) {
				int yPos = y - i;
				int xPos = x - d + i;

				if (yPos >= 0 && xPos >= 0) {
					int& enemy = board[yPos][xPos];
					if (enemy != 0) {
						attack(enemy);
						return;
					}
				}

				i++;
			}

			i = d - 1;

			while (i >= 1) {
				int yPos = y - i;
				int xPos = x + d - i;

				if (yPos >= 0 && xPos < M) {
					int& enemy = board[yPos][xPos];
					if (enemy != 0) {
						attack(enemy);
						return;
					}
				}

				i--;
			}
		}
	}

	void attack(int& enemy) {
		if (enemy == 1) {
			enemy = 2;
			kill++;
		}
	}

	int getKillCount() {
		return kill;
	}
};

void moveEnemy() {
	int temp[15][15];
	memcpy(temp, board, sizeof(temp));

	for (int y = N-1; y >= 0; y--) {
		for (int x = 0; x < M; x++) {
			int state = temp[y][x];
			if (state != 0) {
				if (state == 1) {
					int nextY = y + 1;
					if (nextY < N)
						board[nextY][x] = 1;
				}
				board[y][x] = 0;
			}
		}
	}
}

bool isEndGame() {
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (board[i][j] == 1)
				return false;

	return true;
}

int maximumKillCount() {
	int result = 0;

	for (int i = 0; i < M; i++) {
		for (int j = i + 1; j < M; j++) {
			for (int k = j + 1; k < M; k++) {
				int killCount = 0;

				Archer* archer1 = new Archer(i);
				Archer* archer2 = new Archer(j);
				Archer* archer3 = new Archer(k);

				int backup[15][15];
				memcpy(backup, board, sizeof(backup));

				while (!isEndGame()) {
					archer1->searchEnemy();
					archer2->searchEnemy();
					archer3->searchEnemy();

					moveEnemy();
				}

				killCount += archer1->getKillCount();
				killCount += archer2->getKillCount();
				killCount += archer3->getKillCount();

				result = max(result, killCount);

				memcpy(board, backup, sizeof(board));

				delete archer1;
				delete archer2;
				delete archer3;
			}
		}
	}

	return result;
}

int main(void) {
	cin >> N >> M >> D;
	
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			cin >> board[i][j];

	cout << maximumKillCount() << endl;

	return 0;
}

[문제 링크]

간단한 다이나믹 프로그래밍 문제였다.

입력받은 물품 목록 배열에서, 현재 보고있는 물품의 무게가 준서가 버틸 수 있는 무게보다 무겁지 않을 경우 해당 물품을 가방에 담았을 때 나올 수 있는 최대 가치값과 담지 않았을 때 나올 수 있는 최대 가치값을 비교하여 더 큰 가치값을 선택하도록 구현하면 된다.

따라서 점화식은 다음과 같다.

maxValue = max(dp(here+1, weight + itemWeight) + itemValue , dp(here+1, weight))

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

int N, K, V, W;
int memo[101][100001];

//first : W, second : V
vector<pair<int, int>> item;

int dp(int here, int weight) {
	// 기저사례 : N개의 물건을 모두 탐색했다면 재귀를 종료한다.
	if (here == N) return 0;

	int& ret = memo[here][weight];
	if (ret != -1) return ret;

	if (weight + item[here].first <= K)
		return ret = max(dp(here + 1, weight + item[here].first) + item[here].second, dp(here + 1, weight));
	else
		return ret = dp(here + 1, weight);
}

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

	cin >> N >> K;

	for (int i = 0; i < N; i++) {
		cin >> W >> V;
		item.push_back({ W,V });
	}

	cout << dp(0, 0) << endl;
}

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

원숭이의 좌표와 말처럼 이동할 수 있는 횟수가 몇번 남았는지에 대한 정보, 이동한 횟수를 queue에 담아서 bfs를 수행하면 원하는 결과를 얻을 수 있다.

한가지 유의할 점은 말처럼 이동할 경우 장애물을 뛰어넘을 수 있기 때문에 이미 방문한 좌표라도 말처럼 이동할 수 있는 횟수가 남아있느냐 남아있지 않느냐에 따라 결과값이 달라지게 된다.

따라서, 중복탐색을 피하기 위한 visited 배열을 좌표 정보만 담은 2차원 배열이 아닌, 말처럼 이동한 횟수까지 포함하는 3차원 배열로 선언해야 한다.

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

int K, H, W;
int board[200][200];
bool visited[200][200][31];

int dy[12] = { -1, -2, -2, -1, 1, 2, 2, 1, -1, 0, 0, 1 };
int dx[12] = { -2, -1, 1, 2, -2, -1, 1, 2, 0, -1, 1, 0 };

struct Pos {
	int y;
	int x;
};

int bfs() {
	queue<pair<pair<Pos, int>, int>> q;
	q.push({ { {0,0}, K }, 0 });
	visited[0][0][K] = true;

	while (!q.empty()) {
		int hereY = q.front().first.first.y;
		int hereX = q.front().first.first.x;
		int horse = q.front().first.second;
		int move = q.front().second;

		q.pop();

		if (hereY == H - 1 && hereX == W - 1)
			return move;

		for (int i = 0; i < 12; i++) {
			if (horse <= 0 && i < 8) continue;
			int nextY = hereY + dy[i];
			int nextX = hereX + dx[i];
			if (nextY >= 0 && nextY < H && nextX >= 0 && nextX < W) {
				if (i < 8) {
					if (board[nextY][nextX] == 0 && !visited[nextY][nextX][horse - 1]) {
						q.push({ {{nextY, nextX}, horse - 1 }, move + 1 });
						visited[nextY][nextX][horse - 1] = true;
					}
				}
				else {
					if (board[nextY][nextX] == 0 && !visited[nextY][nextX][horse]) {
						q.push({ {{nextY, nextX}, horse}, move + 1 });
						visited[nextY][nextX][horse] = true;
					}
				}
			}
		}
	}

	return -1;
}
int main(void) {
	cin >> K >> W >> H;

	for (int i = 0; i < H; i++)
		for (int j = 0; j < W; j++)
			cin >> board[i][j];

	cout << bfs() << endl;

	return 0;
}

[문제 링크]

간단한 bfs 문제였다.

수빈이가 +1, -1로 이동하는 경우와, *2로 이동하는 경우에 대해서 bfs를 돌려서 동생을 찾는 가장 빠른 방법을 찾으면 된다.

수빈이가 이동하는 경로를 저장하기 위해 queue에 현재 위치와 그동안 이동했던 경로를 담은 queue를 pair 자료구조에 담았다.

한가지 함정이 있다면, 수빈이가 동생보다 앞에 있을 경우, +1과 *2로 이동하게 되면 반드시 더 멀어지게 되기 때문에 -1로만 이동하게 된다.

극단적인 예로 만약 수빈이가 100000에 위치해 있고, 동생이 0에 위치해 있는 경우 수빈이의 이동경로는 100000 99999 99998 .... 0 이 된다. 이 경로를 queue에 전부 담게 되면 시간복잡도 및 공간복잡도가 매우 커지게 된다.

따라서 시작지점이 수빈이가 동생보다 앞일 경우, bfs를 수행하지 않고 -1로 이동하는 경로를 출력하도록 구현하였다.

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

bool visited[100001];

queue<int> bfs(int N, int K) {
	queue < pair<int, queue<int>>> q;
	q.push({ N, queue<int>({N}) });
	visited[N] = true;

	while (!q.empty()) {
		int here = q.front().first;
		queue<int> route = q.front().second;
		q.pop();

		if (here == K) return route;

		for (int i = 0; i < 3; i++) {
			int next;
			if (i == 0) next = here + 1;
			else if (i == 1) next = here - 1;
			else next = here * 2;

			if (next >= 0 && next <= 100000 && !visited[next]) {
				queue<int> temp = route;
				temp.push(next);
				q.push({ next, temp });
				visited[next] = true;
			}
		}
	}

	return queue<int>();
}

int main(void) {
	int N, K;
	cin >> N >> K;

	if (N >= K) {
		cout << N - K << endl;
		while (N >= K)
			cout << N-- << ' ';
	}
	else {
		queue<int> result = bfs(N, K);

		cout << result.size() - 1 << endl;
		while (!result.empty()) {
			cout << result.front() << ' ';
			result.pop();
		}
	}

	return 0;
}