상경한 개발자 지망생들

문제 링크

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

접근 방법

이 문제는 knapsack 알고리즘의 가장 기본적인 문제이다.

(1) 변수

    dp[i]는 배낭의 가용한 최대 무게가 i일때 담을 수 있는 최대의 가치를 의미한다.

    tmp[i]는dp[i]를 갱신하기 전에 미리 복사를 해놓는 용도로 사용. (dp[i]는 실시간으로 갱신 되기 때문에 갱신된 값이 사용되는 것을 방지하고, dp를 2차원으로 사용하는 것보다 시간적 메모리적 효율이 좋다.) 

(2) solve() 함수

if (item[i].first <= j) {
	dp[j] = max(tmp[j], tmp[j - item[i].first] + item[i].second);
}

    가장 핵심이 되는 부분인데, max()안에서 tmp[j]는 현제 가리키고 있는 물건 item[i]를 담지 않았을 때의 경우이고,

tmp[j - item[i].first] + item[i].second는 item[i]를 담는 경우, item[i]의 무게를 제외한 부분의 가용한 무게에서의 가치의 최댓값 tmp[j - item[i].first]에 현재 item[i]의 가치를 담는 것이다. 그 둘의 값중 더 큰 가치를 가지는 것으로 dp[j]를

갱신하면 된다.

소스 코드

#include <vector>
#include <algorithm>

using namespace std;
pair <int, int> item[101];
int dp[100001]; 
int tmp[100001];
int n, k;

int solve() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			tmp[j] = dp[j];
		}
		for (int j = 1; j <= k; j++) {
			if (item[i].first <= j) {
				dp[j] = max(tmp[j], tmp[j - item[i].first] + item[i].second);
			}
		}
	}
	return dp[k];
}

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		int w, v;
		cin >> w >> v;
		item[i] = { w,v }; //{무게, 가치}
	}
	cout << solve();
}

개발 환경 : VS 2019

질문, 지적 환영입니다.

문제 링크

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

접근 방법

전체적인 순서는 이렇다.

(1) 입력받을 때 모든 치킨집의 좌표 vector에 저장

(2) 저장한 치킨집 vector를 백트래킹하며 가능한 치킨집의 모든 조합에 대하여 치킨거리 계산 후 최솟값 반환

총 K개의 치킨집 중에서 M개 (M<=K)의 치킨집을 뽑은 뒤, 모든 도시에 대해서 뽑은 치킨집과의 치킨거리를 계산한다. 그리고 치킨 거리의 합이 최소인 M에서의 치킨 거리를 출력하는 문제이다.

최대 13개의 치킨집에서 최대 M개까지 뽑아서 최소 치킨 거리를 계산하므로, '조합'의 문제이다.

따라서 백트래킹을 하면서 가능한 치킨집의 모든 조합에 대하여 치킨 거리를 계산한 뒤, 최소 치킨 거리를 출력하면 된다.

백트래킹을 오랜만에 보니 기억이 잘 안나서 이전에 짜놓았던 조합을 참고하였다.

소스 코드

#include <vector>
#include <climits>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 51
using namespace std;
typedef struct coord {
	int y, x;
};
int N, M, map[MAX][MAX], cache_dist[MAX]; // cache_dist[i] : i번째 집의 최소 치킨 거리
vector<coord> chicken, house, selected;
const int INF = 99999999;

int dist(coord& c1, coord& c2) {
	return abs(c1.y - c2.y) + abs(c1.x - c2.x);
}

// h번째 집에 대해서 모든 치킨집과의 거리 계산. 그 중 최소 거리만 남김
int cal_chicken_dist() {
	int ret = 0;
	for (int h = 0; h < house.size(); ++h) {
		int chicken_dist = INF;
		for (int i = 0; i < selected.size(); ++i) {
			chicken_dist = min(chicken_dist, dist(selected[i], house[h]));
		}
		ret += chicken_dist;
	}
	return ret;
}

// 모든 치킨집의 가능한 조합에 대해서 최소 치킨 거리 계산
int nCm(int count, int prev) {
	if (count == M) {
		return cal_chicken_dist();
	}

	int ret = INT_MAX;
	for (int i = prev + 1; i < chicken.size(); ++i) {
		selected.push_back(chicken[i]);
		ret = min(ret, nCm(count + 1, i));
		selected.pop_back();
	}
	return ret;
}

// 최소 M개의 치킨집은 존재
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			cin >> map[i][j];
			if (map[i][j] == 1)
				house.push_back({ i, j });
			else if (map[i][j] == 2)
				chicken.push_back({ i, j });
		}
	}
	cout << nCm(0, -1);
	return 0;
}

개발 환경 : VS2019

질문, 지적 환영합니다!

문제 링크

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

접근 방법

문제를 읽다가 '거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.부분과 더 큰 물고기는 지나갈 수 없다는 조건에서 BFS 알고리즘의 문제라는 것을 깨닫고, BFS로 문제 풀이를 시작했다. 풀다보니 전형적인 BFS의 형식에 귀찮은 조건이 몇 가지 추가된 꼴이었다.

소스 코드

코드에 주석을 많이 남겨놨습니다. :) 복잡한 계산이 있는 문제가 아니니, 코드로 참고 부탁드려요!

#include <queue>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 21
#define NUM_DIRECTION 4
using namespace std;
typedef struct coord {
	int y, x, size, time;
};
int N, map[MAX][MAX], visit[MAX][MAX], expp = 0;
coord shark; // 아기 상어의 좌표 및 크기
// vector<coord> fishs; // 물고기들의 좌표 및 크기
vector<coord> eatable_fishs;
const coord direction[NUM_DIRECTION] = { {0, 1, 0, 0}, {0, -1, 0, 0}, {1, 0, 0, 0}, {-1, 0, 0, 0} };

bool comp(const coord& a1, const coord& b1) {
	if (a1.time == b1.time) { // 시간이 동일하다면, y가 작은 순으로
		if (a1.y == b1.y) { // y도 동일하다면 x가 작은 순으로
			return a1.x < b1.x;
		}
		return a1.y < b1.y;
	}
	return a1.time < b1.time; // 시간이 작은 순으로
}

bool isRanged(int y, int x) {
	if (y >= N || x >= N || y < 0 || x < 0) return false;
	return true;
}

void search_eatable() {
	queue<coord> q;
	memset(visit, 0, sizeof(visit)); // 현재 위치에서 시간 계산을 다시 해야하므로 초기화
	eatable_fishs.clear(); // 현재 위치에서 시간 계산을 다시 해야하므로 초기화
	visit[shark.y][shark.x] = 1;
	q.push(shark);
	coord cur;
	int ny, nx;
	while (!q.empty()) {
		cur = q.front();
		q.pop();
		for (int i = 0; i < NUM_DIRECTION; ++i) {
			ny = cur.y + direction[i].y;
			nx = cur.x + direction[i].x;
			if (isRanged(ny, nx) && !visit[ny][nx] && map[ny][nx] <= shark.size) { 
				// 범위 내에 있고, 방문하지 않았으며, 지나가야 하므로 크기가 더 작다면
				if (map[ny][nx] != 0 && shark.size > map[ny][nx])
					// 먹을 수 있는 물고기라면? 물고기 백터에 넣음
					eatable_fishs.push_back({ ny, nx, map[ny][nx], cur.time + 1 });
				visit[ny][nx] = 1;
				q.push({ ny, nx, 0, cur.time + 1 });
			}
		}
	}
}

// 경험치를 체크하여 사이즈와 같아졌다면 사이즈업, 경험치 초기화
void check_exp() {
	if (expp >= shark.size) {
		++shark.size;
		expp = 0;
	}
}

// eatable_fish의 물고기를 먹고, 해당 자리로 이동하며, 소요된 시간을 반환한다.
int move_and_eat(coord eatable_fish) {
	map[shark.y][shark.x] = 0; // 자리를 비운다.
	map[eatable_fish.y][eatable_fish.x] = 9; // 먹어치운 물고기의 좌표로 이동한다.
	shark.y = eatable_fish.y;
	shark.x = eatable_fish.x;
	++expp; // 경험치 +1
	check_exp();
	return eatable_fish.time;
}

int solve() {
	int ret = 0;
	while (1) {
		search_eatable(); // 현재 위치에서 물고기들과의 거리 및 크기 계산
		if (!eatable_fishs.empty()) { // 먹을 수 있는 물고기가 존재한다면
			sort(eatable_fishs.begin(), eatable_fishs.end(), comp); // 좌표 순으로 정렬
			ret += move_and_eat(eatable_fishs.front()); // 가장 가까운 물고기를 먹는다.
		}
		else // 먹을 수 있는 물고기가 존재하지 않는다면
			break;
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	memset(visit, 0, sizeof(visit));
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			cin >> map[i][j];
			if (map[i][j] != 0) { // 빈 칸이 아니라면
				if (map[i][j] == 9) { // 아기 상어라면
					shark.y = i;
					shark.x = j;
					shark.size = 2; // 초기 크기 = 2(조건)
					shark.time = 0;
				}
			}
		}
	}
	cout << solve();
	return 0;
}

개발 환경은 VS2019입니다.

질문, 지적, 덧글 환영합니다!

문제 링크

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

접근 방법

복잡한 알고리즘성 문제가 아닌 시뮬레이션 문제였습니다.

주사위를 4가지 방향으로 굴렸을때 각 면의 값이 어떻게 이동하는지 그림을 그려보면서 접근하였고, 매번 이동을 진행하기 전에 좌표에 대한 검사를 진행하였습니다. dice[6] 배열을 선언하여 주사위의 각면에 번호를 매겨서 접근하였지만, 번호로 보니 햇갈려서 각 번호 면에 대하여 참조 변수를 알아보기 쉽게 선언하였습니다.

아래와 같이 각 면을 참조한 뒤, 설명대로 주사위를 움직입니다. 움직일 때 마다 주사위의 면의 값 뿐만 아니라, 좌표 이동도 해줍니다.

int& north = dice[0],

west = dice[1], 

top = dice[2], 

east = dice[3], 

south = dice[4], 

bot = dice[5];

이동이 끝난 뒤에는 현재 위치의 지도값이 0인지, 0이 아닌지에 따라 다른 처리를 해주었고, 만약 이동할 수 없는 경우 함수 자체에서 false를 반환하였고, 이동이 성공한 경우 true를 반환하여 지도값에 따른 처리를 해주었습니다.

처음에 입력으로 주는 주사위의 초기 위치를 x, y 거꾸로 받아서 한참을 해맸는데, 아마 이 부분 실수하는 분들이 많을 것 같습니다.

소스 코드

#include <cstring>
#include <iostream>
#define MAX 21
#define MAXK 1001
#define NUMD 5
#define NUM_DICE 6
using namespace std;
typedef struct coord {
	int y, x;
};
int N, M, K, map[MAX][MAX], cmd[MAXK];
coord cur;
int dice[6];
const coord direction[NUMD] = { {0, 0}, {0, 1}, {0, -1}, {-1, 0}, {1, 0} }; // 0, 동, 서, 북, 남
int& north = dice[0], west = dice[1], top = dice[2], east = dice[3], south = dice[4], bot = dice[5];

// 0 = north
// 1 = west
// 2 = top
// 3 = east
// 4 = south
// 5 = bot

bool isRanged(int y, int x) {
	if (y >= N || x >= M || y < 0 || x < 0) return false;
	return true;
}

bool move_dice(int d) {
	int ny, nx;
	int temp;
	ny = cur.y + direction[d].y;
	nx = cur.x + direction[d].x;
	if (!isRanged(ny, nx)) return false;
	if (d == 1) { // 동
		temp = east;
		east = top;
		top = west;
		west = bot;
		bot = temp;
	}
	else if (d == 2) { // 서
		temp = west;
		west = top;
		top = east;
		east = bot;
		bot = temp;
	}
	else if (d == 3) { // 북
		temp = north;
		north = top;
		top = south;
		south = bot;
		bot = temp;
	}
	else { // 남
		temp = bot;
		bot = south;
		south = top;
		top = north;
		north = temp;
	}
	cur.y = ny;
	cur.x = nx;
	return true;
}

void solve() {
	for (int k = 0; k < K; ++k) {
		if (move_dice(cmd[k])) { // 움직였다면
			if (map[cur.y][cur.x] == 0) { // 지도칸이 0이라면
				map[cur.y][cur.x] = bot;
			}
			else { // 지도칸이 0이 아니라면, 칸의 수가 주사위 바닥으로 복사, 칸은 0
				bot = map[cur.y][cur.x];
				map[cur.y][cur.x] = 0;
			}
			cout << top << "\n";
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M >> cur.y >> cur.x >> K;
	memset(dice, 0, sizeof(dice));
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < M; ++j)
			cin >> map[i][j];
	for (int k = 0; k < K; ++k) cin >> cmd[k]; // 1: 동, 2: 서, 3: 북, 4: 남
	solve();
	return 0;
}

개발 환경은 VS 2019입니다.

질문, 지적 환영합니다. 감사합니다!!

문제 링크

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

접근 방법

처음에는 정말 단순하게 오름차순으로 정렬해서 크기순으로 합치는 접근법을 사용했으나, 오답이 나왔습니다.

여러 블로그를 참고하여 인접한 파일끼리 합친다는 접근 방법을 적용하여 분할 정복 + DP 느낌으로 풀었습니다.

소스 코드

MAX를 501로 두고, SUM[0] = 0으로 두었습니다.

sum[a] = 0 ~ 파일 a까지의 비용의 합입니다.

cache[a][b] = 구간 [a, b]를 합치는데 드는 최소 비용입니다.

따라서 cache[a][a] = 0입니다. (합칠 구간이 없으므로)

cache[a][a+1] = sum[a + 1] - sum[a - 1]입니다.

cache[a][a + 2] = min(cache[a][a] + cache[a+1][a+2], cache[a][a+1] + cache[a+2][a+2]) + sum[a+2] - sum[a] 입니다.

더 큰 구간에 대한 문제는

cache[a][b] = min(cache[a][b], cache[a][a+mid] + cache[mid+1][b])에서 mid를 a부터 b - 1까지 반복함으로써 최소 비용을 구합니다. ( a <= b )

#include <climits>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 501
using namespace std;
int sum[MAX], cache[MAX][MAX], cost[MAX];

int divide(int low, int high) {
	if (low >= high) return 0;
	int& ret = cache[low][high];
	if (ret != -1) return ret;
	ret = INT_MAX;
	for (int mid = low; mid < high; ++mid) {
		ret = min(ret, divide(low, mid) + divide(mid + 1, high) + sum[high] - sum[low - 1]);
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T, K;
	cin >> T;
	for (int t = 0; t < T; ++t) {
		cin >> K;
		memset(sum, 0, sizeof(sum));
		memset(cache, -1, sizeof(cache));
		sum[0] = 0;
		for (int i = 1; i <= K; ++i) {
			cin >> cost[i];
			sum[i] = sum[i - 1] + cost[i];
		}
		cout << divide(1, K) << "\n";
	}
	return 0;
}

Visual Studio 2019 사용하였습니다.

질문, 지적 환영입니다!