아인스트라세의 SW 블로그

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

문제설명

백준저지 17825번 문제, 주사위 윷놀이 풀이입니다.

문제를 보면 나름 복잡해 보이는 윷놀이 판이 있고, 이 윷놀이 판에서 주사위를 10번 던져서 그 주사위의 눈금값이 고정되어 있을 때, 어떻게 하면 최대 점수를 얻느냐 대략 이런문제입니다.

문제에서 설명이 좀 부족한 부분으로는, 윷판에 써잇는 숫자가 그 곳에 오르면 얻게 되는 점수이고, 빨간색 화살표는 기본적으로 이동하는 길입니다. 파란색의 화살표는 파란색 큰 동그라미 위치에 말이 놓였을때 이동하는 경로입니다.

윷놀이에 대한 기본적인 규칙은 다들 알 것이라고 생각해서, 해당 부분 설명 부분은 간단하게 한 느낌입니다.

문제 해결 전략 설정

일단 말이 4가지가 있고 각 10번의 이동 중 각각 이동마다 1,2,3,4번 말 중 어떤 말을 움직일지를 결정해야 합니다.

10번마다 독립적인 4가지의 선택지가 있고, 따라서 총 결정할 수 있는 방법은 //(4^{10}//)이 되겠습니다.

이 값은 //(2^{20}//)의 값과 동일하며, //((2^{10})^{2} = 1024^2 = 1048576//)입니다.

100만정도 되는 양으로 1초안에 충분히 계산할 수 있는 계산량입니다. 보통 1억번 연산에 1초로 생각하시면 편합니다.

따라서 모든 경우의 수를 다 따져보아도 충분히 풀리는 문제이므로, 완전탐색으로 해결할 수 있습니다.

구현전략

말의 개수가 4가지이고, 10개의 독립적인 선택지를 고르는 방식이므로, 이러한 경우 비트마스킹(bitmasking)을 이용해서 구현하면 편리합니다.

비트는 0과 1로 바이너리(2가지)이지만, 2비트를 사용하면 00,01,10,11로 4가지를 표현할 수 있습니다. 따라서 2*10=20 비트만 사용하면 해당 경우의 수를 모두 표현할 수 있습니다.

모든 경우의 수를 모두 순회하는 방식은 비트마스킹을 이용한다고 할 때, 각각의 윷놀이 말이 움직이는 것을 시뮬레이션을 해서 점수를 구해야 합니다.

윷 판의 형태가 규칙성을 찾기 힘든 형태이지만, 총 33개 칸에 주사위가 1~5의 숫자만 나오므로 룩업테이블(look-up table)을 사용할 만 합니다.

아래와 같이 그림을 그려서 룩업 테이블을 구성해 보았습니다.

빨간색은 칸에 부여한 번호이고, 노란색은 칸에서 얻는 점수입니다.

코드

구현한 코드입니다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int dice[10];
#define END 32

//이동 규칙이 복잡할 수 있으므로 Look-up 테이블을 만들어서 사용한다.
//jump[index][0] = 해당 판 점수
//jump[index][1~5] => 주사위 해당 수가 나오면 이동하는 양
int jump[33][6] = {
	{0,1,2,3,4,5}, //0번자리
	{2,2,3,4,5,9}, //1번자리
	{4,3,4,5,9,10}, //2번자리
	{6,4,5,9,10,11}, //3번자리
	{8,5,9,10,11,12},//4번자리
	{10,6,7,8,20,29},//5번자리
	{13,7,8,20,29,30}, //6번자리
	{16,8,20,29,30,31}, //7번자리
	{19,20,29,30,31,32}, //8번자리
	{12,10,11,12,13,14}, //9번자리
	{14,11,12,13,14,15}, //10번자리
	{16,12,13,14,15,16}, //11번자리
	{18,13,14,15,16,17}, //12번자리
	{20,18,19,20,29,30}, //13번자리
	{22,15,16,17,24,25}, //14번자리
	{24,16,17,24,25,26}, //15번자리
	{26,17,24,25,26,27}, //16번자리
	{28,24,25,26,27,28}, //17번자리
	{22,19,20,29,30,31}, //18번자리
	{24,20,29,30,31,32}, //19번자리
	{25,29,30,31,32,32}, //20번자리
	{26,20,29,30,31,32}, //21번자리
	{27,21,20,29,30,31}, //22번자리
	{28,22,21,20,29,30}, //23번자리
	{30,23,22,21,20,29}, //24번자리
	{32,26,27,28,31,32}, //25번자리
	{34,27,28,31,32,32}, //26번자리
	{36,28,31,32,32,32}, //27번자리
	{38,31,32,32,32,32}, //28번자리
	{30,30,31,32,32,32}, //29번자리
	{35,31,32,32,32,32}, //30번자리
	{40,32,32,32,32,32}, //31번자리
	{0,32,32,32,32,32} //32번자리
};
int ans;
void check(int bit) {
	int score = 0;
	int occupation[35];
	int pos[4];
	memset(occupation, 0, sizeof(occupation));
	memset(pos, 0, sizeof(pos));
	occupation[0] = 4;

	for (int turn = 0; turn < 10; turn++) {
		//이번에 옮길 말
		int horse = (bit >> (turn * 2)) & 0x3;

		//이동하는 거리
		int move = dice[turn];

		//현재 위치
		int& current_pos = pos[horse];

		//이동할 위치
		int next_pos = jump[current_pos][move];

		//이번 이동으로 얻을 점수
		int get_score = jump[next_pos][0];

		//처음이나 끝 위치가 아닌데 말이 겹치는 경우
		if (occupation[next_pos] > 0 && next_pos && next_pos != END) {
			//불가능한 이동
			return;
		}
		else {
			score += get_score;
			occupation[next_pos]++;
			occupation[current_pos]--;
			current_pos = next_pos;
		}
	}
	ans = max(ans, score);
}
int main() {
	for (int i = 0; i < 10; i++)
		cin >> dice[i];
	for (int bit = 0; bit < (1 << 20); bit++) {
		check(bit);
	}
	cout << ans << endl;

}

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

문제 개요

백준저지 17822번 문제 원판 돌리기 문제 풀이입니다.

규칙에 따라 원판을 돌리고, 인접 수를 지우고, 수를 변경하고 하는 식의 문제입니다.

하라는대로 하면 되는 시뮬레이션 문제에 해당합니다.

N, M, T값이 50으로 작은편이므로, 원판을 죄다 돌려버리고 돌릴때 마다 다 체크를 한다고 해봅시다.

1번 돌릴때 마다 인접한 원판 수들을 체크를 해야하는데, 최대 원판에 쓰인 수의 개수는 N * M개 이므로 최대 50*50 = 2500개입니다.

2500개의 수를 50번 확인한다고 하면 125,000번으로 12만 5천번 정도됩니다.

그리고 그 때 마다 원판위의 숫자들을 shift한다고 하면, 모든 원판의 수를 다 shift하고 그 양이 50과 같이 큰 값이라 하면

50^4 = 6,250,000으로 625만번입니다. shift하는 것을 한번씩 여러번 반복하는 식으로 매우 대충 구현한다는 가정하에 대충 이정도 값이 나옵니다.

그런데 shift하는 것은 한번에 점프뛰는 방식으로도 가능하기 때문에 이정도까지도 안나옵니다.

고로 결론은, 그냥 그대로 따라하는 시뮬레이션 방식으로 구현해도 충분히 시간안에는 들어오는 크기의 N,M,T 값이라는 것입니다.

(대충 1억번 연산에 1초 정도 걸린다고 봅니다.)

구현 전략

원판 돌리는 연산을 간편하게 하기 위해서 bias라는 배열을 따로 두고, [원판][위치] 의 값을 읽거나 쓸 때에는 별도의 getter, setter 함수를 만들어서 코드를 작성해 보았습니다.

이녀석의 원리를 조금 설명드려 보자면 예를들어 다음과 같은 원판이 있다고 칩시다. 한 원판에 숫자가 4개 쓰여있으니 M=4가 됩니다.

12시 부터 시계방향으로 숫자를 읽는다면 1,2,3,4 가 되겠지요?

이 원판을 시계방향으로 90도 돌리면 다음과 같은 모양이 됩니다.

마찬가지로 12시 부터 읽는다면 4,1,2,3이 됩니다.

이를 잘라서 평평하게 핀다고 생각해봅시다.

그러면 초기의 1,2,3,4는 다음 모양과 같게 나옵니다.

그리고 시계방향으로 90도 돌린 4,1,2,3은 다음과 같게 나옵니다.

실제로 C언어 배열에는 위와 같이 연속된 메모리에 값이 저장이 되겠지요. 근데 그렇다면 한번 원판을 돌릴 때 마다 4개(M개)의 칸의 값을 모두 바꾸어 주어야 하는데, 발상을 조금 바꾸어봅시다.

값은 맨 처음 그대로 1,2,3,4로 저장을 하되, 읽는 순서만 바꾸는 거죠.

처음 1,2,3,4가 나오기 위해서는 인덱스 읽는 순서를 0,1,2,3으로 읽고, 시계방향으로 90도 돌린 경우는 인덱스를 3,0,1,2의 순서로 읽는것입니다.

그러면 아까처럼 값을 바꾸는 경우와 똑같은 값이 나오게 됩니다.

마찬가지로, 반시계방향으로 90도 돌린 경우는 인덱스를 1,2,3,0의 순서로 읽게 되겠지요?

따라서 원판이 시계방향으로 돌리게 되면 bias값에 -1을 해 줄것이고, 반시계 방향으로 돌리게 되면 bias값에 +1를 해줍니다.

시계방향으로 한번 돌리고 반시계 방향으로 한번 돌리면 결론적으로 원래 자리로 돌아오게 되는데 bias값에는 이러한 점도 적용이 되게 됩니다.

즉 bias값은 맨 처음 값을 몇 번째 인덱스부터 읽을 것인지를 나타내게 되는 것이지요.

하지만 bias값이 4보다 크거나 음수가 나타날 수 있으니, 이 bias값이 0이상 3이하(M-1)의 값만 나오게 하도록 모듈러(나머지)연산을 해 줍니다.

음수의 경우 모듈러 연산을 해도 음수가 나오기 때문에 4(M값)만큼을 더해서 0이상 3이하의 값이 나오게 되는 것입니다.

디버깅을 위해서 dump함수도 작성했는데, 활성화 하기 위해서는 dump 함수의 return 값을 제거하고 사용하시면 됩니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define DEL 99999
int num[55][55];
int bias[55];
int N, M, T;
typedef pair<int, int> pii;
void dump(const char[]);
int get_num(int i, int j) {
	//i번째 원판의 j번째 위치 녀석 값 가져오기
	j += bias[i];
	while (j < 0) {
		j += M;
	}
	j %= M;
	return num[i][j];
}
void set_num(int i, int j, int v) {
	//i번째 원판의 j번째 위치 녀석 값을 v로 셋팅
	j += bias[i];
	while (j < 0) {
		j += M;
	}
	j %= M;
	num[i][j] = v;
}
void process() {
	//인접수 날리고, 값 조정 한번에 하는 함수
	bool changed = false;
	vector<pii> del; //지울 수 좌표들 모음
	del.clear();

	//같은 원판 사이에 인접한 수들 찾아내기
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			int a = get_num(i, j);
			int b = get_num(i, j + 1);
			if (a != DEL && b != DEL && a == b) {
				del.push_back({ i,j });
				del.push_back({ i,j + 1 });
				changed = true;
			}
		}
	}
	//다른 원판 사이에 인접한 수들 찾아내기
	for (int i = 0; i + 1 < N; i++) {
		for (int j = 0; j < M; j++) {
			int a = get_num(i, j);
			int b = get_num(i + 1, j);
			if (a != DEL && b != DEL && a == b) {
				del.push_back({ i, j });
				del.push_back({ i + 1, j });
				changed = true;
			}
		}
	}

	//지울 녀석들 모아서 지우기
	for (auto p : del) {
		set_num(p.first, p.second, DEL);
	}
	dump("지운뒤");

	//지운 수가 없으면 계속 진행
	if (changed) return;

	int cnt, sum;
	cnt = sum = 0;
	//지워지지 않은 수와, 그 수들의 총합 을 구함
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (num[i][j] != DEL) {
				cnt++;
				sum += num[i][j];
			}
		}
	}

	//남은 수들이 평균보다 크면 -1, 작으면 +1 시킴.
	//나누기를 안쓰는 이유는 정수 소수점 잘리는 부분 때문
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (num[i][j] != DEL) {
				if (num[i][j] * cnt > sum) {
					num[i][j]--;
				}
				else if (num[i][j] * cnt < sum) {
					num[i][j]++;
				};
			}
		}
	}
	dump("덧뺄샘이후");
}
int main() {
	cin >> N >> M >> T;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> num[i][j];
		}
	}
	while (T--) {
		//회전 시킬 값들 받기
		int x, d, k;
		cin >> x >> d >> k;
		int v = x;
		int shift = k * (d == 0 ? -1 : +1);
		dump("돌리기전");
		while (v <= N) {
			//bias 배열에다가 값을 더하는식으로, 회전시킴
			bias[v-1] += shift;
			v += x;
		}
		dump("돌린뒤");
		//인접수 지우고 하는 처리들을 여기서 함
		process();
	}

	//남은 수 다 더해서 출력
	int ans = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (num[i][j] != DEL) {
				ans += num[i][j];
			}
		}
	}
	cout << ans << endl;

}
void dump(const char str[]) {
#ifndef WIN32
	return;
#endif
	puts(str);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cout << get_num(i, j) << ' ';
		}
		cout << endl;
	}
	cout << "============================" << endl;
}

이번 주말에는 아무것도 없는 줄 알았다가, 킥스타트 Remind 메일을 보고 토요일 밤에 구글 킥스타트가 있는것을 알고 참여했다.

구글 킥스타트는 구글 코드잼과 비슷한 대회인데, 다른 점은 각각의 라운드가 독립적인 하나 뿐이라는 것.

구글 코드잼은 예선전(Qualification Round)부터 Round 1,2,3이후 월드파이널 온사이트 대회로 넘어가는 방식으로 각 단계에서 사람수를 줄여가는 식의 서바이벌 방식의 대회라고 볼 수 있다.

킥스타트는 대학생들 대상으로 채용을 목적으로하는 대회로, 각각의 독립 라운드가 날짜별로 시간대별로 포진되어있다.

A,B,C 등등과 같은 방식으로 라운드를 구분한다.

따라서 하려는 라운드가 우리 한국시각으로는 새벽이더라도, 다른 한국시각으로 낮이나 저녁시간대인 다른 대회를 참여하면 되는 것이다.

결론부터 말하면 385등으로 총 3문제 중, 2.5문제를 풀었다.

뭔가 거의 다 푼 것 같아서 기분은 좋다.

3번째 문제 Hidden Test case는 날려먹엇는데, 풀이가 올라왔으니 차근차근 읽어봐야 할듯.

1번 문제 Book Reading은 대충 설명해보면, 배수를 찾는 문제이다.

1~N 페이지인 책 중 M개의 페이지가 찢겨져 나가있고, Q명의 독자는 각각 자신이 원하는 수의 배수에 해당하는 책 페이지만 읽는다 했을때, 독자들이 읽은 페이지의 총 개수를 구하면 된다.

책이 찢겨지지 않았다고 했을때는, 배수만 구해서 죄다 더해버리면 된다. 다만 찢긴 페이지를 어떻게 처리하냐가 관건이다.

Visible을 맞추기 위해서는 각각 독자별로 찢겨진 페이지에 얼마나 해당되는지만 체크하면 된다. Brute Force로 풀리는 크기로 N,M,Q가 1000이하이다.

Visible을 맞추기 위한 코드이다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
ll solve() {
	int N, M, Q;
	scanf("%d%d%d", &N, &M, &Q);
	ll ans = 0;
	vector<int> torn(M);
	vector<int> reader(Q);
	for (int i = 0; i < M; i++) {
		cin >> torn[i];
	}
	for (int i = 0; i < Q; i++) {
		cin >> reader[i];
		ans += (ll)N / reader[i];
	}

	for (auto tt : torn) {
		for (auto rdr : reader) {
			if (tt % rdr == 0) {
				ans--;
			}
		}
	}
	return ans;
}
int main() {
	int tc;
	scanf("%d", &tc);
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: %lld\n", t, solve());
	}
}

Hidden을 맞추기 위해서는 좀 더 효율적인 코드가 필요하다.

찢겨진 페이지들을 소인수 분해한 뒤, 약수를 모두 다 구해서 해당 약수들에 cnt배열 값을 1씩 증가시키는 방식으로 독자를 쿼리를 최적화 해 보았다. 될지 안될지는 긴가 민가 했는데, 대충 통한듯.

소수들은 에라토스테네스의 채를 이용해서 구했다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define MAXN 100005
bool sieve[MAXN]; //false == prime
int cnt[MAXN];
vector<int> primes;
bool is_prime(int n) {
	if (n < 2) return false;
	if (n == 2) return true;
	for (int i = 2; i*i <= n; i++) {
		if (n % i == 0) return false;
	}
	return true;
}
void get_sieve() {
	sieve[0] = sieve[1] = true;
	for (int n = 2; n < MAXN; n++) {
		if (sieve[n] == false && is_prime(n)) {
			int base = n * 2;
			while (base < MAXN) {
				sieve[base] = true;
				base += n;
			}
		}
	}
	for (int i = 2; i < MAXN; i++) {
		if (sieve[i] == false) {
			primes.push_back(i);
		}
	}
}
void factorize(int n, vector<pair<int, int>>& factors) {
	while (n > 1) {
		for (int prime : primes) {
			if (prime > n) break;
			int cnt = 0;
			while (n % prime == 0) {
				n /= prime;
				cnt++;
			}
			if (cnt) {
				factors.push_back(make_pair(prime, cnt));
			}
		}
	}
}
void get_divisors(int n, vector<pair<int, int>>& factors, int k) {
	if (k == (int)factors.size()) {
		cnt[n]++;
		//cout << "got divisor = " << n << endl;
		return;
	}
	get_divisors(n, factors, k + 1);
	int exp = factors[k].second;
	for (int dec = 1; dec <= exp; dec++) {
		factors[k].second -= dec;
		n /= factors[k].first;
		get_divisors(n, factors, k + 1);
		factors[k].second += dec;
	}
	n *= pow(factors[k].first, exp);
	

}
ll solve() {
	memset(cnt, 0, sizeof(cnt));
	int N, M, Q;
	scanf("%d%d%d", &N, &M, &Q);
	ll ans = 0;
	vector<int> torn(M);
	vector<int> reader(Q);
	for (int i = 0; i < M; i++) {
		cin >> torn[i];
	}
	for (int i = 0; i < Q; i++) {
		cin >> reader[i];
		ans += (ll)N / reader[i];
	}
	for (int i = 0; i < M; i++) {
		vector<pair<int, int>> factors;
		factors.clear();
		factorize(torn[i], factors);
		get_divisors(torn[i], factors, 0);
	}

	for (auto rdr : reader) {
		ans -= cnt[rdr];
	}
	return ans;
}
int main() {
	get_sieve();
	int tc;
	vector<pair<int, int>> factors;

	scanf("%d", &tc);
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: %lld\n", t, solve());
	}
}

2번 문제는 약간 수학적인 문제같이 생겻는데, N개의 A숫자가 있고 숫자 M이 있을때

(A1 ^ k) + (A2 ^ k) + ... + (An ^ k) <= M을 만족하는 최대 k를 구하면 된다.

Visible은 모든 k에 대하여 다 해보고 최대 값을 구하는 완전탐색으로 풀린다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
ll A[1003];
int bitmap[20];
ll solve() {
	memset(bitmap, 0, sizeof(bitmap));
	ll ans = -1;
	int N;
	ll M;
	cin >> N >> M;
	ll sum = 0;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	for (ll k = 0; k <= 1000; k++) {
		ll ss = 0;
		for (int i=0; i < N; i++) {
			ll& a = A[i];
			ss += (a^k);
			if (ss > M) break;
		}
		if (ss <= M) {
			ans = max(ans, k);
		}
	}
	return ans;
	
	
}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: %lld\n", t, solve());
	}
}

Hidden은 좀더 효율적인 방법이 필요한데, 어차피 10^16이면 50비트 남짓이라는 것을 이용해서, 받는 A 숫자들을 비트별로 개수를 다 세어놓는다.

해당 비트 사용수가 과반수이면, 즉 N/2보다 크면, k의 해당 비트를 1로 해서 비트 들을 Inverse시켜주는 식으로 한번 전처리 한뒤,

M과 지금 다 합친 값과 여유분을 계산을 해서 , k의 가장 큰 bit를 xor해서 inverse해줘도 되는 경우 bit를 1로 set하는 식으로 구해보았다.

멍청하게 bitmap 배열을 20으로 잡아서(10^20을 생각) 런타임 에러가 막 났었는데 2^50이니 50이상 잡았어야 했다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
ll A[1003];
int bitmap[60];
ll solve() {
	memset(bitmap, 0, sizeof(bitmap));
	ll ans = 0;
	int N;
	ll M;
	cin >> N >> M;
	ll sum = 0;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		sum += A[i];
		for (int j = 0; j <= 50; j++) {
			if (A[i] & (1LL << j)) {
				bitmap[j]++;
			}
		}
	}

	for (int i = 0; i <= 50; i++) {
		if (bitmap[i] * 2 >= N) {
			ans |= (1LL << i);
			sum += (1LL << i) * (N - bitmap[i] * 2);
		}
	}
	//if (sum > M) return -1LL;

	for (int i = 50; i >= 0; i--) {
		if ((1LL << i) & ans) continue;
		ll diff = M - sum; //여유분
		ll cost = (1LL << i) * (N - bitmap[i] * 2);
		if (cost <= diff) {
			ans |= (1LL << i);
			sum += cost;
		}
	}
	if (sum > M) return -1LL;
	return ans;

}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: %lld\n", t, solve());
	}
}

3번 문제는 교대근무를 하는 2명의 직원이 있고, 각 근무시간은 최소 한명이상 근무해야하며, 근무 시 얻는 Happiness를 합한 값이 각각 H를 넘는 경우의 수를 구하는 그런문제다.

문제를 딱 보고 어렵다 생각했는데 Visible N값이 12로 완전탐색을 조져도 될 것이라는 생각이 들었다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
ll A[22], B[22];
ll solve() {
	ll ans = 0;
	int N;
	ll H;
	cin >> N >> H;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> B[i];
	}
	ll AH, BH;
	for (int bit = 1; bit < (1 << N); bit++) {
		AH = 0;
		//BH = 0;
		for (int i = 0; i < N; i++) {
			if (bit & (1 << i)) {
				AH += A[i];
			}
			
		}
		if (AH < H) continue;
		
		
		for (int bbit = 1; bbit < (1 << N); bbit++) {
			BH = 0;
			for (int i = 0; i < N; i++) {
				if (bbit & (1 << i)) {
					BH += B[i];
				}
			}
			if (BH < H) continue;
			if ((bit | bbit) != ((1 << N) - 1)) continue;
			ans++;
		}
		
	}
	return ans;
}
int main() {
	int tc;
	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: %lld\n", t, solve());
	}
}

Hidden으로 N=20은 도저히 어떻게 해야할 지 생각이 안나서 스킵해놓은 상태이다. 이따가 풀이보고 공부해봐야겠다.

완전탐색으로 풀면 된다.

dfs로 모든 경우를 모두 체크하면 되며 재귀함수호출로 구현하면 간단하다.

dfs(int day) 함수는 day번째 날 부터 최대 벌 수 있는 돈의 양을 리턴하게 된다.

각각의 경우 상담을 하거나 / 하지 않거나의 두가지 선택지가 있는데,

상담을 할 시, 상담 완료 기간만큼 시간이 지나고, 상담해서 받을 수 있는 금액을 얻게 된다.

상담을 하지 않을 시, 금액을 얻지 못하지만, 곧바로 다음 날 있는 상담을 선택할 지 말지를 결정할 수 있게 된다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int T[20], P[20];
int N;
int dfs(int day) { //day번째 날 부터 벌 수 있는 최대 돈
    if (day >= N) return 0;
    int ret = 0;
    if (T[day] + day <= N) {
        ret = max(ret, dfs(day + T[day]) + P[day]);
    }
    if (day + 1 < N)
        ret = max(ret, dfs(day + 1));
    return ret;
}
int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> T[i] >> P[i];
    }
    cout << dfs(0) << endl;
}

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

배열 돌리기 시리즈 첫번째 문제입니다.

N, M이 최대 300으로 값이 그리 크지 않으므로, 정말 하나하나 다 돌려보면 답이 나옵니다.

가장 바깥부터 해서 R만큼 돌린 위치에 값을 저장하는 식으로 코드를 작성해 보았습니다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int A[303][303];
int B[303][303];
const int mx[] = { +1, +0, -1, +0 };
const int my[] = { +0, +1, +0, -1 };
int main() {
	int N, M, R;
	scanf("%d%d%d", &N, &M, &R);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &A[i][j]);
		}
	}
	pii p[4];
	int sero = N - 1;
	int garo = M - 1;
	int round = 2 * (sero + garo);
	int stage = 0;

	p[0].first = p[0].second = stage;

	p[1].first = sero;
	p[1].second = stage;

	p[2].first = sero;
	p[2].second = garo;
	
	p[3].first = stage;
	p[3].second = garo;

	while (garo > 0 && sero > 0) {
		// Process (Write to B)
		int rotate = R % round;
		int sx, sy, dx, dy;
		sx = dx = p[0].first;
		sy = dy = p[0].second;
		int d1, d2;
		d1 = d2 = 0;
		for (int i = 0; i < rotate; i++) {
			dx += mx[d2];
			dy += my[d2];
			if (dx == p[(d2 + 1) % 4].first && dy == p[(d2 + 1) % 4].second) {
				d2 = (d2 + 1) % 4;
			}
		}
		for (int i = 0; i < round; i++) {
			B[dx][dy] = A[sx][sy];
			sx += mx[d1];
			sy += my[d1];
			if (sx == p[(d1 + 1) % 4].first && sy == p[(d1 + 1) % 4].second) {
				d1 = (d1 + 1) % 4;
			}
			dx += mx[d2];
			dy += my[d2];
			if (dx == p[(d2 + 1) % 4].first && dy == p[(d2 + 1) % 4].second) {
				d2 = (d2 + 1) % 4;
			}
		}

		// Process End
		sero -= 2;
		garo -= 2;
		round -= 8;
		stage += 1;
		p[0].first = p[0].second = stage;

		p[1].first = stage + sero;
		p[1].second = stage;

		p[2].first = stage + sero;
		p[2].second = stage + garo;

		p[3].first = stage;
		p[3].second = stage + garo;
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			printf("%d", B[i][j]);
			if (j + 1 < M) putchar(' ');
		}
		putchar('\n');
	}
}

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

백준저지 17472번 문제 다리 만들기 2문제입니다.

N, M이 10으로 크지 않고 섬의 개수도 6개 밖에 안되므로, 하나하나씩 직접 찾아가도 크게 문제가 없습니다.

대충 단계는 다음과 같습니다.

1. Flood Fill로 모든 섬 찾기

2. 다리를 놓을 수 있는 모든 경우를 체크 함

3. 섬을 Graph의 Vertex로, 다리를 놓는 경우를 Edge로 모델링함

4. 그래프에 대한 최소 스패닝 트리(MST: Minimum Spanning Tree)를 구한다.

5. MST의 길이를 리턴, MST를 구할 수 없는 경우 -1를 리턴.

1번은 재귀를 이용한 dfs로 간단하게 짯으며(find_island 함수), 하는 과정에 물과 맞닿아 있는 좌표는 별도로 표기를 했습니다.

2번은 try_bridge 함수에서 체크를 했고, 한쪽 방향으로 계속 전진하며 다른 섬을 만나거나 맵 밖으로 나갈때까지 전진한 뒤 다리의 조건이 되는지를 체크했습니다.

4번은 MST를 크루스칼 알고리즘을 이용해서 구했습니다. Edge를 가장 짧은 길이순으로 소팅한 뒤, 하나씩 포함할 것인지 아닌지를 DSU(Disjoint Set 혹은 Union Find 자료구조)로 체크하면서 합쳤습니다.

코드입니다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int N, M;
int field[11][11];

#define NOT_FOUND -1
#define WATER 0
//섬은 1~6의 숫자 값을 갖는다.
struct Pos {
	int x, y;
};
struct Bridge {
	int src, dest, len;
	bool operator<(const struct Bridge& rhs) const {
		return len < rhs.len;
	}
};
bool isin(Pos p) {
	return p.x >= 0 && p.y >= 0 && p.x < N && p.y < M;
}
struct Island {
	vector<Pos> edge; //물과 맞닿아있는 지점 좌표(다리 지을 수 있는지 체크용)
};
vector<Bridge> bridges;
Island islands[7];
const Pos d[4] = { {0, +1}, {+1, 0}, {-1, 0}, {0, -1} };
void find_island(Pos pos, int id) {
	field[pos.x][pos.y] = id;
	int water = 0;
	for (int k = 0; k < 4; k++) {
		Pos nx = { pos.x + d[k].x, pos.y + d[k].y };
		if (isin(nx)) {
			if (field[nx.x][nx.y] == NOT_FOUND) {
				find_island(nx, id);
			}
			else if (field[nx.x][nx.y] == WATER) {
				water++;
			}
		}
	}
	if (water) {
		islands[id].edge.push_back(pos);
	}
}
void try_bridge(const Pos pos) {
	const int id = field[pos.x][pos.y];
	for (int k = 0; k < 4; k++) {
		Pos p = { pos.x + d[k].x, pos.y + d[k].y };
		int len = 0;
		int dest = 0;
		while (isin(p) && field[p.x][p.y] == 0) {
			p.x += d[k].x;
			p.y += d[k].y;
			len++;
		}
		if (isin(p)) {
			dest = field[p.x][p.y];
		}
		if (len >= 2 && dest) {
			bridges.push_back({ id, dest, len });
		}
	}
}
int dsu[7];
int dsu_find(int p) {
	while (dsu[p] != p) {
		p = dsu[p];
	}
	return p;
}
int main() {
	int island_cnt = 1;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> field[i][j];
			if (field[i][j]) field[i][j] = -1;
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (field[i][j] == NOT_FOUND) {
				dsu[island_cnt] = island_cnt;
				find_island({ i, j }, island_cnt++);
			}
		}
	}
	for (int i = 1; i < island_cnt; i++) {
		for (Pos p : islands[i].edge) {
			try_bridge(p);
		}
	}

	// 최소 스패닝 트리 만들기
	sort(bridges.begin(), bridges.end());
	int total_len = 0;
	for (auto b : bridges) {

		if (dsu_find(b.src) != dsu_find(b.dest)) {
			total_len += b.len;
			// Disjoint Set Merge
			dsu[dsu_find(b.src)] = dsu_find(b.dest);
		}
	}

	// 최소 스패닝 트리에 모든 섬이 포함되었는지 확인
	int dsu_first = dsu_find(1);
	for (int i = 2; i < island_cnt; i++) {
		if (dsu_first != dsu_find(i)) {
			total_len = -1;
		}
	}
	cout << total_len << endl;
	return 0;
}

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

올라온 지 얼마 안된 따끈따끈한 문제이다.

일단 대충 문제만 보면 그래프 문제에, 좀 빡새보이는데

문제 제한을 보면 N값이 2~10로 매우 작다.

이러한 점을 고려해서 모든 케이스를 고려하는 브루트 포스(Brute-force) 방식으로 문제를 푼다면 시간 복잡도는 대략

//(O(N2^N)//)이 된다.

왜냐면, 구역은 N개가 있고, 각각이 A아니면 B 선거구에 속해야 한다. 

각각의 구역은 2가지 경우의 수가 있고, 동시에 일어날 수 있으므로 2를 N번 곱한 경우의 수, 즉 //(2^N//)가지 경우의 수가 나온다.

각각의 경우에, dfs나 bfs등으로 flood-fill 식으로 인접한 녀석들을 다 탐색 한 뒤, 각각의 선거구가 한 덩어리인지 확인하기 위해서는 //(N//)의 시간이 걸리므로, //(O(N2^N)//)와 같은 시간복잡도가 나오게 된다.

이 시간복잡도에 Worst case의 //(N=10//)을 대입하면 대략 10만정도의 값이 나오는데,

이는 CPU 1초에 대략 1억번 정도의 연산을 한다는 가정을 해도 0.01초 만에 해결할 수 있는 계산량이다.

구역을 2가지로 나누는 것은 비트마스킹을 이용해서 for문 하나로 해결을 했고,

구역이 Valid하게 나뉘었는지는 각각 dfs를 한번 씩 해서, 선거구를 모두 cover하는지를 확인했다.

아래는 코드이다.

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321

int ans;
int n;
int p[11];
vector<int> edge[11];
set<int> visit;
void dfs(int v, set<int>& s) {
	for (int next : edge[v]) {
		if (visit.find(next) == visit.end() && s.find(next) != s.end()) {
			visit.insert(next);
			dfs(next, s);
		}
	}
}
bool is_equal(set<int>& a, set<int>& b) {
	if (a.size() != b.size()) return false;
	set<int>::iterator p1 = a.begin();
	set<int>::iterator p2 = b.begin();
	for (int i = 0; i < a.size(); i++) {
		if (*p1 != *p2) return false;
		p1++;
		p2++;
	}
	return true;
}
void check(int bit) {
	set<int> a, b;
	int aval, bval;
	aval = bval = 0;
	for (int i = 0; i < n; i++) {
		int v = (1 << i);
		if (bit & v) {
			a.insert(i);
			aval += p[i];
		}
		else {
			b.insert(i);
			bval += p[i];
		}
	}
	//if (a.size() == 0 || b.size() == 0) return;

	visit.clear();
	visit.insert(*a.begin());
	dfs(*a.begin(), a);
	if (is_equal(visit, a) == false) return;

	visit.clear();
	visit.insert(*b.begin());
	dfs(*b.begin(), b);
	if (is_equal(visit, b) == false) return;
	
	ans = min(ans, abs(aval - bval));
}
int main() {
	ans = INF;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> p[i];
	for (int i = 0; i < n; i++) {
		int v; cin >> v;
		while (v--) {
			int t; cin >> t;
			edge[i].push_back(t - 1);
		}
	}
	for (int bit = 1; bit + 1 < (1 << n); bit++) {
		check(bit);
	}
	if (ans == INF) ans = -1;
	cout << ans << endl;
}

문제에서는 인덱스를 1부터 센다는 것을 체크를 안해서 2번 틀리긴 했다. ㅠㅠ

그런데 왜 기본 TC는 맞게 나오는가!

https://www.acmicpc.net/category/detail/340

한국정보올림피아드 초등부 2010년도 문제 풀이입니다.

총 3문제가 있습니다.

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

1번 용액 (백준 2467)

1번 용액 문제입니다.

1번 문제치곤 조금 난이도가 있는 문제라고 생각합니다.

처음에는 바이너리 서치를 이용해서 O(NlgN)으로 풀이를 해 보았습니다.

A번째 용액, B번째 용액을 골라서 확인을 하되, A번째 용액에 대해서는 for문 을 돌고, 각각 A번째용액에 대하여, B번째 용액을 결정할 때, 바이너리 서치 개념을 적용해서 풀어보았습니다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int a[100005];
int n;
int f, s, val;
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", a + i);
	}
	f = a[0];
	s = a[1];
	val = abs(f+s);
	for (int i = 0; i < n - 1; i++) {
		int first = a[i];

		int left = i + 1; // [left, right]
		int right = n - 1;
		while (left < right) {
			int mid = (left + right) / 2;
			int& second = a[mid];
			int sum = first + second;
			if (sum < 0) {
				if (abs(sum) < val) {
					val = abs(sum);
					f = first;
					s = second;
				}
				left = mid + 1;
			}
			else if (sum > 0) {
				if (abs(sum) < val) {
					val = abs(sum);
					f = first;
					s = second;
				}
				right = mid;
			}
			else {
				cout << first << ' ' << a[mid] << endl;
				return 0;
			}
		}
		int second = a[right];
		int sum = first + second;
		if (abs(sum) < val) {
			val = abs(sum);
			f = first;
			s = second;
		}
		second = a[left];
		sum = first + second;
		if (abs(sum) < val) {
			val = abs(sum);
			f = first;
			s = second;
		}
	}
	cout << f << ' ' << s << endl;
	return 0;
}

이 풀이 외에도 O(N)으로도 풀이가 가능하다는 것을 알게 되었습니다.

배열이 정렬되어 있기 때문에, A번째에서 A+1번째로 이동할 때, 더 0에 가까운 값을 구하기 위해서는 B에서 B-1로 이동하는 경우는 있을 수 있으나 B+1에서 더 0에 가까운 값이 나올 수는 없기에 그리디하게 투포인터 형식으로 풀 수있습니다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int arr[100005];
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", arr + i);
	}
	int a, b, val;
	a = arr[0], b = arr[n - 1];
	val = abs(a + b);
	int left = 0;
	int right = n - 1;
	while (left < right) {
		int l, r, sum;
		l = arr[left];
		r = arr[right];
		sum = l + r;
		if (abs(sum) < val) {
			val = abs(sum);
			a = l;
			b = r;
		}
		if (sum > 0) {
			right--;
		}
		else {
			left++;
		}
	}
	printf("%d %d\n", a, b);
}

코드도 훨씬 간단합니다.

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

2번 안전영역 (백준 2468)

2번 문제 안전영역입니다.

N값이 100으로 별로 크지 않으므로, BFS혹은 DFS로 Flood-Fill해서 안전지역 개수를 세면 되고, 높이 값이 1~100이므로, 100번 해 주면 됩니다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int field[101][101];
bool visit[101][101];
int n;
bool isin(int x, int y) {
	return x >= 0 && y >= 0 && x < n && y < n;
}
const int dx[] = { +1, -1, +0, +0 };
const int dy[] = { +0, +0, +1, -1 };
void dfs(int x, int y, int h) {
	//visit[x][y] = true;
	for (int k = 0; k < 4; k++) {
		int nx = x + dx[k];
		int ny = y + dy[k];
		if (isin(nx, ny) && field[nx][ny] > h) {
			if (visit[nx][ny] == false) {
				visit[nx][ny] = true;
				dfs(nx, ny, h);
			}
		}
	}
}
int check(int h) {
	int ret = 0;
	memset(visit, 0, sizeof(visit));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (visit[i][j] == false && field[i][j] > h) {
				visit[i][j] = true;
				ret++;
				dfs(i, j, h);
			}
		}
	}
	return ret;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> field[i][j];
		}
	}
	int ans = 1;
	for (int i = 1; i <= 101; i++) {
		ans = max(ans, check(i));
	}
	cout << ans << endl;
	return 0;
}

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

3번 사다리 타기 (백준 2469)

3번 사다리 타기 문제입니다.

사다리를 타서 모양을 맞출 수 있느냐와 관련된 문제입니다.

양방향 dfs의 개념을 적용하면 간단하게 풀어 볼 수 있습니다.

Meet in the middle 이라는 개념과도 좀 비슷할 수 있습니다.

시작 시 알파뱃 배치와 종료시 알파뱃 배치 둘다 알기 때문에, 위에서 내려오고 아래에서 올라와서 모르는 사다리 배치 전후의 배열을 알아냅니다.

그리고 그 전 후 배열을 사다리 한 줄로 적용해서 변환 가능한지에 따라 풀어내면 됩니다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
void fail(int k) {
	while (--k) {
		cout << 'x';
	}
	cout << endl;
	exit(EXIT_SUCCESS);
}
int main() {
	string lines[1005];
	int k, n;
	int q;
	cin >> k >> n;
	string first;
	string fin;
	string ans = "";
	cin >> fin;
	for (int i = 0; i < k; i++) {
		first += ('A' + i);
	}
	for (int i = 0; i < n; i++) {
		cin >> lines[i];
		if (lines[i][0] == '?') q = i;
	}
	for (int i = 0; i < q; i++) {
		for (int j = 0; j < lines[i].length(); j++) {
			char& ch = lines[i][j];
			if (ch == '-') {
				swap(first[j], first[j + 1]);
			}
		}
	}
	for (int i = n - 1; i > q; i--) {
		for (int j = 0; j < lines[i].length(); j++) {
			char& ch = lines[i][j];
			if (ch == '-') {
				swap(fin[j], fin[j + 1]);
			}
		}
	}

	for (int i = 0; i < k - 1; i++) {
		char up = first[i];
		char down = fin[i];
		if (up != down) {
			ans += "-";
			if (i + 2 < k) {
				ans += "*";
				i++;
			}
		}
		else {
			ans += "*";
		}
	}
	for (int i = 0; i < ans.length(); i++) {
		if (ans[i] == '-') {
			swap(first[i], first[i + 1]);
		}
	}
	if (first != fin) fail(k);
	cout << ans << endl;
}

한국정보올림피아드 (KOI) 2018년도 초등부 문제 풀이입니다.

https://www.acmicpc.net/category/detail/1894

백준저지에서 문제를 확인 / 풀이가 가능합니다.

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

1번 행복 (백준 15969)

1번 행복 문제입니다.

아주 간단한 문제이죠. 최대값과 최소값을 구해서 뺀 뒤 출력하면 됩니다.

파이썬2으로 풀어보았습니다.

input();a=map(int,raw_input().split());print max(a)-min(a)

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

2번 화살표 그리기 (백준 15970)

2번 화살표 그리기 문제입니다.

그리디하게 가장 가까운 녀석들에 화살표를 잇고 그 길이를 모두 더하면 되는 문제입니다.

색상이 흑과 백, 2가지만 나오지 않고 N가지가 나온다는 점에 유의 하여

색깔별로 다른 vector에 저장한 뒤, 정렬하여 인접한 녀석 중 가까운 곳에 잇는 방식으로 풀 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
vector<int> A[5005];
int main() {
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int pos, col;
		cin >> pos >> col;
		A[col-1].push_back(pos);
	}
	for (int i = 0; i < N; i++) {
		sort(A[i].begin(), A[i].end());
	}
	int ans = 0;
	for (int j = 0; j < N; j++) {
		for (int i = 0; i < A[j].size(); i++) {
			int prev, next;
			prev = next = 987654321;
			if (i > 0) {
				prev = A[j][i] - A[j][i - 1];
			}
			if (i + 1 < A[j].size()) {
				next = A[j][i + 1] - A[j][i];
			}
			ans += min(prev, next);
		}
	}
	cout << ans << endl;
	return 0;
}

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

3번 두 로봇 (백준 15971)

3번 두 로봇 문제입니다.

그림만 봐도 Graph 문제인 것을 알 수 있겠죠?

총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다. N개의 방은 1번부터 N번까지의 번호를 붙여 1번 방, 2번 방, …, N번 방으로 부른다. 통로는 정확히 N-1개가 발견되었는데, 각각 서로 다른 두 방 사이를 연결시켜 주며 중간에 다른 통로와 이어지는 경우는 없다고 한다. 또한 이 통로들을 이용하여 임의의 두 방 사이를 이동하는 것이 가능하며, 임의의 두 방 사이를 이동할 때 같은 통로를 두 번 이상 지나지 않는 경로는 유일한 것으로 밝혀졌다.

이 조건을 보아서, 이 Graph는 트리입니다.

서로 다른곳에 있는 로봇이 만나기 위해 이동해야 하는 거리의 최소값을 구해야 합니다. 두 점의 최단거리 문제이죠.

그리고 한 Edge에 대해서는 이동하지 않고 통신을 할 수 있기 때문에, 그냥 최단거리 문제는 아닙니다.

Edge의 Weight값이 균일하지 않기 때문에 Dijkstra Shortest Path 알고리즘으로 풀 수 있으며, 한 Edge의 값은 제거할 수 있기 때문에 지난 Edge 중 가장 큰 Edge weight 값을 가지고 있다가, 총 거리에서 해당 Largest Edge weight를 제거하면 정답이 됩니다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;

#define MAXN 100005
vector<pii> edges[MAXN];
bool visit[MAXN];

struct State {
	int pos, totallen, maxseg;
	bool operator<(const State& rhs) const {
		return totallen > rhs.totallen;
	}
};
int main() {
	int N, A, B;
	cin >> N >> A >> B;
	for (int i = 1; i < N; i++) {
		int src, dst, len;
		cin >> src >> dst >> len;
		edges[src].push_back(make_pair(dst, len));
		edges[dst].push_back(make_pair(src, len));
	}
	priority_queue<State> pq;
	pq.push({ A, 0, 0 });
	while (pq.size()) {
		State state = pq.top(); pq.pop();
		int pos = state.pos;
		visit[pos] = true;
		if (pos == B) {
			cout << (state.totallen - state.maxseg) << endl;
            return 0;
		}
		for (auto next : edges[pos]) {
			int next_pos = next.first;
			int next_seglen = next.second;
			if (visit[next_pos] == false) {
				pq.push({ next.first, state.totallen + next_seglen, max(state.maxseg, next_seglen) });
			}
		}
	}

}

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

4번 물탱크 (백준 15972)

4번 물탱크 문제입니다.

아이디어를 생각해내기 좀 어려웠는데요, 풀고 나서도 왜 이게 풀렸는지 지금 100% 이해가 된 상태는 아닙니다.

일단 Graph 문제로 환원하여 생각을 하였고, 외부와 직/간접적으로 연결된 녀석들은 물이 셀 수 있습니다.

직접적으로 연결된 녀석은 그 연결된 구멍의 높이만큼 물이 세어나가게 되고, 간접적으로 연결된 녀석은 조건에 따라서 물이 세어나갈수도 있고 아닐 수도 있습니다.

외부에서 부터 Graph 탐색을 한다고 하였을 때, 간접적으로 외부와 연결된 내부 공간들이 탐색이 되게 되는데, 

이때 외부로 연결되는 구멍의 높이가 높아지는 경우와 낮아지는 경우가 있습니다. 

외부와 연결되는 구멍의 높이가 높아지는 경우는 최근 구멍의 높이만큼 물이 줄줄 세개 됩니다.

구멍의 높이가 낮아지는 경우는, 최근 연결된 녀석의 수심만큼만 물이 줄줄 세어나가게 됩니다.

이러한 특징을 활용해서 변형된 Dijkstra 최단거리 알고리즘으로 문제를 풀이했습니다.

구멍 높이가 낮은 녀석부터 먼저 탐색하도록 하였고, 이게 문제가 풀릴지 아닐지 몰랐는데, 풀리긴 하더군요.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;

struct Edge{
	int x, y, h;
};
struct State {
	int x, y, sx, sy, h;
	bool operator<(const struct State& rhs) const {
		return h > rhs.h;
	}
};
vector<Edge> edges[1005][1005];
int height[1005][1005];
bool visit[1005][1005];

int main() {
	int N, M, H;
	scanf("%d%d%d", &N, &M, &H);

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			height[i][j] = H;
		}
	}

	for (int i = 0; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			/*
			(i,j) ~ (i+1, j)
			*/
			int v;
			scanf("%d", &v);
			if (~v) {
				edges[i][j].push_back({ i + 1, j, v });
				edges[i + 1][j].push_back({ i, j, v });
			}
		}
	}
	for (int j = 1; j <= N; j++) {
		for (int i = 0; i <= M; i++) {
			/*
			(j, i) ~ (j, i+1)
			*/
			int v;
			scanf("%d", &v);
			if (~v) {
				edges[j][i].push_back({ j, i + 1, v });
				edges[j][i + 1].push_back({ j, i, v });
			}
		}
	}
	priority_queue<State> pq;
	for (int i = 0; i <= M + 1; i++) {
		int x = 0;
		int y = i;
		visit[x][y] = true;
		for (auto next : edges[x][y]) {
			pq.push({ next.x, next.y, x, y, next.h });
		}
	}
	for (int i = 0; i <= M + 1; i++) {
		int x = N + 1;
		int y = i;
		visit[x][y] = true;
		for (auto next : edges[x][y]) {
			pq.push({ next.x, next.y, x, y, next.h });
		}
	}

	for (int i = 1; i <= N; i++) {
		int x = i;
		int y = 0;
		visit[x][y] = true;
		for (auto next : edges[x][y]) {
			pq.push({ next.x, next.y, x, y, next.h });
		}
	}
	for (int i = 1; i <= N; i++) {
		int x = i;
		int y = M + 1;
		visit[x][y] = true;
		for (auto next : edges[x][y]) {
			pq.push({ next.x, next.y, x, y, next.h });
		}
	}

	while (pq.size()) {
		auto state = pq.top(); pq.pop();
		int x = state.x;
		int y = state.y;
		int sx = state.sx;
		int sy = state.sy;
		int h = state.h;
		if (visit[x][y] == false) {
			visit[x][y] = true;
			height[x][y] = min(height[x][y], max(h, height[sx][sy]));
			for (auto eg : edges[x][y]) {
				if (visit[eg.x][eg.y] == false) {
					pq.push({ eg.x, eg.y, x, y, eg.h });
				}
			}
		}
	}

	int ans = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			ans += height[i][j];
		}
	}
	printf("%d\n", ans);

	return 0;
}

- 이 글은 [2019-11-22]에 마지막으로 업데이트 되었습니다. 실제 최신 정보와 맞지 않는 부분이 있을 수 있습니다.

- 본 글은 지극히 주관적인 입장에서 작성되었습니다. 틀린부분이나 의견 등이 있다면 댓글로 편하게 알려주세요.

- 본 글은 삼성계열사에 입사하고자 하는 사람들에게 도움이 될 만한 정보를 주기 위해 작성되었습니다.

SW 역량테스트란?

삼성전자에 소프트웨어 직군으로 신입 채용을 준비하는 사람이라면 한번 쯤 들어봤을 단어 일 겁니다.

바로 SW 역량 테스트죠!

매 년, 상반기 / 하반기 마다 조금씩 상이할 수는 있지만 대체적으로 신입 공채는 서류전형 + SW역량테스트 + 면접 + 건강검진의 프로세스로 이루어지게 됩니다. 

 일반적으로 대기업 공채 프로세스에서 인적성 시험에 해당하던(GSAT)는 소프트웨어 직군으로 지원하는 지원자는 SW 역량테스트로 대체 됩니다. 간단하게 말하면 코딩 시험이죠.

상시 테스트란?

그리고 이 SW 역량 테스트는 공채 지원시 외에도 시험을 쳐 볼수 있습니다.

이 시험을 상시 테스트라고 부르도록 하겠습니다.

상시 테스트는 난이도별로 A형, B형, C형으로 나뉘는데요, 등급이라고 보시면 되고, 난이도 순은 A형 < B형 < C형입니다.

A형 등급을 취득하면 B형 시험을 칠 자격이 생기고, 마찬가지로 B형 등급을 취득하면, C형 등급을 칠 자격이 생깁니다.

해당 난이도의 시험을 1회 이상 통과하게 되면 해당 상시 테스트의 등급을 취득하게 되는데요,

이 등급을 취득하면 삼성 계열사(삼성전자, SDS, 미라콤, 세메스 등)에 SW 직군 신입사원으로 지원 시 가산점 등의 혜택을 받게 됩니다.

각각 등급 별로 난이도 차이가 생각보다 꽤 많이 나는 편이니, 차근차근 공부하면서 실력을 향상시킨다고 목표를 잡으시면 좋습니다.

특히나 C형의 난이도는 매우 어려우며, 삼성에서 매년 주최하는 대학생 대상 프로그래밍 대회인 SCPC에서 입상하면 C형 취득한 것과 비슷한 대우를 해준다고 하니, 그 난이도가 어느정도 일지는 대충 예측할 만 합니다.

특히나 B형 이상 취득자정도의 실력이라면, 흔히 우리가 이름을 들어볼만한 대기업이나 IT기업에서 신입사원 공채 코딩테스트 정도는 뿌시고 들어갈 정도는 됩니다.

공채 시 치게 되는 SW 역량테스트의 난이도는 상시 테스트 A형과 거의 같다고 보시면 됩니다.

A형은 삼성전자에 SW 직군으로 입사하기 위한 최소 요건이 되겠습니다.

A형을 취득한 사람은 B형에 응시할 수 있고, B형에 취득한 사람은 C형에 응시할 수 있습니다.

이 상시시험은 https://swexpertacademy.com/main/sst/intro.do 여기 링크에서 신청을 할 수 있습니다.

이 시험을 신청할 수 있는 SW 익스퍼트 아카데미라는 사이트는 삼성전자 및 SDS에서 주관하여 운영하는 사이트입니다.

해당 사이트에 계정을 만든 뒤 상시 테스트를 신청할 수 있는데, 예전에는 아니었지만 요즘은 최근 한달 간 해당 사이트에서 특정 난이도에 해당하는 문제들을 일정 이상 풀어야지 신청이 가능합니다.

따라서 평소에 저 사이트를 방문해서 문제들을 조금 씩 풀어주는 것이 좋겠지요?

하지만 시험이 그렇게 자주 있지는 않고(몇달에 한번 정도 열리는 것 같습니다), 예전에 이 상시 시험이 유명하지 않았을

때에는 시험을 신청해서 산책 다녀오듯 한번 시험 치고 오면 되었었는데,

요즘엔 이 시험 신청하는 것 조차 대학교 수강신청 하는 것 마냥 경쟁이 치열해졌습니다.

그래서 작년 말쯤에는 A형 시험 신청이 열리는 아침에 서버가 터져서 몇일간 담당자분이 야근하시면서 서버 복구를 한 적도 있었다고 합니다.

이러한 열기는 아마 쉽게 식을 것 같지는 않아 보입니다.

취업 경쟁이 점점 치열해지는 것이 이러한 이유 중 하나라고 생각합니다.

어쨋든, 요즘은 A형 상시 테스트가 조금 개편이 되어서, 1문제를 풀던 기존과는 다르게 2개의 문제를 3시간 동안 풀게 되는데

1개의 문제를 완벽히 풀게 되면 A등급을 취득하고, 2개의 문제를 완벽히 풀게 되면 A+등급을 취득하게 됩니다. A나 A+ 등급을 취득하게 되면 삼성전자 공채 지원시 우대하게(가산점을 받습니다) 됩니다. 붙을 확률이 높아지는 것이죠. 물론 A+ 등급이 A등급보다 우대하는 것이 더 좋습니다.

삼성전자 기준으로, A등급은 서류 전형에서만 우대를 하고, A+등급은 서류 전형 및 SW 역량테스트에서 우대를 합니다.

이전에는 A+ 등급 취득자는 SW 역량테스트를 면제시켜줬는데, 지금은 면제를 시켜줄 지 아닌지는 확실치 않습니다.

(우대라고만 써있습니다.) 이번 공채까지는 A+ 취득자를 역량테스트 면제를 시켜 줄 수도 있지만 다음에는 안시켜 줄 수 도 있습니다.

삼성 전자는 이러한 부분에 대해서는 상당히 깔끔한 식으로 공지를 한다고 보시면 됩니다. 예컨데, 마케팅 직무 분야 지원 시, 대학 전공 무관이라고 쓰여 있으면 실제로 전공 무관입니다. 역량테스트에 우대라고 쓰여있으면 실제로도 우대입니다.

디테일한 부분은 올해 공채와 다음해 공채에 계속 바뀔 수 있겠지만, 어쨋든 확실한 것은, 삼성전자에서 이 코딩테스트 역량을 중요시 하고 있고, 이 등급이 높은 사람을 채용하려는 의지가 강하다는 것과,

이 상시 테스트에서 높은 등급을 취득하면 입사가 쉬워진다는 것이죠. (우리 모두 알고리즘 공부 열심히 합시다)

공채 시험(SW역량테스트)시에는 3시간동안 2문제를 풀게 되는데, 합격을 하려면 적어도 1문제라도 완벽하게 풀어야 합니다.

여기서 완벽히 푼다는 것은, 해당 문제에 대하여 있는 모든 TestCase에 대하여 Pass가 되어야 한다는 뜻입니다.

문제를 풀 때에는 샘플용 Test Case를 대략 5개 정도 주는데, 실제 채점할때는 좀더 촘촘하고 많은 데이터로 채점을 합니다.

Sample Test Case를 모두 맞추더라도, 실제 채점 데이터에서 Fail이 날 수 있습니다. Sample Test Case에서 Fail이 난다면, 실제 채점 데이터는 당연히 Fail이겠지요.

시험 환경

시험 환경은 오프라인 시험입니다. 삼성전자 인재개발원과 같은 장소에 날짜 및 시각을 정해서 가는 시험이라서, 물리적인 한계 때문에 한번에 시험을 칠 수 있는 사람의 수가 제한되어 있습니다. 그래서 요즘은 시험 신청하는 것도 치열해 지는 것이 그러한 이유 때문이겠지요.

시험을 치러 갈 때에는 본인이 편한 복장에 신분증을 지참해야 합니다.

필기구 같은 경우는 가져가도 상관은 없지만, 본인이 가져온 종이나 노트 등은 사용할 수 없습니다.

대신 시험장에서 나누어주는 연습장(모눈종이 같은 것)을 2장 정도 지급해 줄 것이고, 필기구도 없다고 하면 빌려줍니다. 검정색 볼펜을 빌려 줄 것입니다.

그리고 연습장과 빌린 필기구는 시험을 종료하고 시험장을 떠날 때 반납해야 합니다.

시험장 컴퓨터는 일반 데스크탑 컴퓨터이고, 윈도우즈 10 운영체재가 설치되어 있을 것입니다.

시험장 컴퓨터에서는 당연히 인터넷은 막혀있고,  개발 도구로는 Visual Studio / pyCharm / Eclipse가 설치되어 있고 각각 C/C++, Python, Java 사용자를 위한 개발도구 입니다.

그 외의 프로그램은 메모장과 계산기만 사용가능합니다.

시험장 갈때 팁

상시 테스트의 고사장은 다양하지만, 그 중 한곳은 용인 서천에 위치한 삼성전자 인재개발원입니다.

인재개발원의 경우 교통이 불편하므로, 미리 3~40분 정도 더 여유 시간을 갖고 출발하는 것이 좋습니다.

인재개발원과 가장 가까운 지하철 역은 영통역으로 수원시에 포함되는 지역이지만, 인재개발원은 용인시에 포함되지만 차량 이동 거리는 15분 정도 밖에 되지 않습니다.

따라서 택시 입장에서는, 짧은 거리임에도 불구하고 시계에 해당되기 때문에, 인재개발원으로 갈 때에는 손님을 태울 수 있지만, 수원으로 다시 돌아올 때에는 손님을 태울 수 없으므로 택시기사분들이 선호하지 않습니다.

달리 말하면 카카오 택시 등이 잘 잡히지 않는다는 뜻입니다. 카카오 택시가 아닌 길거리에서 택시를 잡으려고 하더라도 택시가 잘 잡히는 지역은 아닙니다. (더군다나 시험에 늦는 상황이라면 잘 보이지 않는 택시가 너무나도 야속하게 느껴지겠지요)

택시를 타려면 오히려 영통역 전에 일찌감치 내려서 잡는것이 더 잘 잡히고 빠르고 안전하게 도착할 수 있습니다.(지갑은 비어갑니다.)

그렇다고 영통역에서 마을버스를 타고 이동하려고 하면, 마을 버스의 배차간격이 생각보다 길기 때문에(10분 이상) 빠듯하게 출발했다가는 시험장에 늦게 도착할 수 있습니다.

그나마 안정적인 방법은 영통역 홈플러스에서 55번 마을 버스를 타고 이동하는 방법인데, 버스 노선이 어느정도 돌아가므로 여유 시간을 갖고 출발하는 것이 가장 좋습니다.

영통역에서 인재개발원까지 걸어서 이동한다면 3~40분 정도 소요되므로 , 인재개발원은 매우 교통적으로 애매하고 불편한 곳에 위치해 있다고 볼 수 있습니다.

이 점 참고 하시여 어렵게 신청한 시험에 늦지 않도록 합시다.

------------------------------------------------------------

삼성 역량테스트 및 A형 테스트에 대한 정보 외에도 삼성 역량테스트 및 A형 테스트를 준비하는 분들을 위한 제가 제안하는 공부 커리큘럼 & 로드맵을 보고 싶으신 분은 링크를 클릭해주시면 됩니다.

해당 글로 이동

---------------------------------------------------------------