[2021 acm-icpc] 7/4 연습 문제

1. 백준 2159번 - 케익 배달 (Gold 2 - DP)

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

2159번: 케익 배달

 

풀이

 

문제의 핵심은 크게 2가지이다.

 

1. 주문이 들어온 순서대로 배달되기를 원함

2. 케익을 받는 고객의 위치까지 가거나 고객의 상하좌우 인접 격자점에 가야함

 

1번의 조건에 따라 i번째 최단 거리는 반드시 i-1번째 최단거리의 영향을 받는다.

따라서 앞서 구했던 최단거리들을 저장해놓고 사용한다 -> Dynamic Programming

 

2번의 조건에 따라 최단거리는 총 5개의 점 중 한 곳이다.

 

X	0, 1	X
-1, 0	0, 0	1, 0
X	0, -1	X

(이때 주의해야 할 점은 양수 좌표계이기 때문에 위로 올라가면 y좌표는 증가한다.)

이때 고객이 위치한 (0, 0) 좌표는 절대 최단거리가 될 수 없기 때문에 결과적으론 4군데만 확인하면 된다.

 

즉 각각의 고객마다 이전 고객의 상하좌우 4좌표와 자신의 상하좌우 4좌표의 최단거리, 총 16가지 경우의 수 중 최단거리를 구하면 된다.

 

(쉽게 풀어써보면

각 고객의 상하좌우를 아래와 같이 1~4로 표현한다면

 

X	1	X
2	고객	3
X	4	X

min(

i-1번째 고객의 1번 위치부터 i번째 고객의 1번 위치까지의 최단거리,

i-1번째 고객의 1번 위치부터 i번째 고객의 2번 위치까지의 최단거리,

i-1번째 고객의 1번 위치부터 i번째 고객의 3번 위치까지의 최단거리,

i-1번째 고객의 1번 위치부터 i번째 고객의 4번 위치까지의 최단거리,

i-1번째 고객의 2번 위치부터 i번째 고객의 1번 위치까지의 최단거리,

i-1번째 고객의 2번 위치부터 i번째 고객의 2번 위치까지의 최단거리,

i-1번째 고객의 2번 위치부터 i번째 고객의 3번 위치까지의 최단거리,

i-1번째 고객의 2번 위치부터 i번째 고객의 4번 위치까지의 최단거리,

...

i-1번째 고객의 4번 위치부터 i번째 고객의 3번 위치까지의 최단거리,

i-1번째 고객의 4번 위치부터 i번째 고객의 4번 위치까지의 최단거리)

이다.

 

소스 코드(.cpp)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

ll dp[100007][9];
vector<pll>cake;
ll dx[] = { 1, -1, 0, 0 };
ll dy[] = { 0, 0, 1, -1 };

int main() {
	ll n, sx, sy, ex, ey;
	cin >> n;
	cin >> sx >> sy;
	for (ll i = 0; i < n; i++) {
		cin >> ex >> ey;
		cake.push_back(pll(ex, ey));
	}
	// 첫 고객 초기화
	for (ll i = 0; i < 4; i++) {
		ll nx = cake[0].first + dx[i];
		ll ny = cake[0].second + dy[i];
		dp[0][i] = abs(nx - sx) + abs(ny - sy);
	}
	for (ll i = 1; i < n; i++) {
		ll x = cake[i].first;
		ll y = cake[i].second;
		for (ll k = 0; k < 4; k++) {
			ll nx = x + dx[k];
			ll ny = y + dy[k];
			ll temp = LLONG_MAX;
			for (ll j = 0; j < 4; j++) {
				ll px = cake[i - 1].first + dx[j];
				ll py = cake[i - 1].second + dy[j];
				// 16가지의 경우의 수 중 가장 최소값을 찾는다
				temp = min(temp, dp[i - 1][j] + abs(nx - px) + abs(ny - py));
			}
			dp[i][k] = temp;
		}
	}
	ll ans = LLONG_MAX;
	for (ll i = 0; i < 4; i++) {
		ans = min(ans, dp[n - 1][i]);
	}
	cout << ans << "\n";
}

# Long Long을 써야 되는지 확인은 안해봤는데 일단 안전하게 Long Long을 사용하긴 했다.

# 다 풀고 생각해보니 10만 * 10만 좌표(최단거리 = 20만)를 중복 가능하게 최단거리로 10만번 반복하는 최악의 경우에는 20만 * 10만 =  2*10^10, 즉 int 범위를 넘어가므로 Long Long을 써야 하는게 맞다. 

 

2. SCPC 2019 2차 예선 1 - 소수 수열 (DP)

풀이

1. 에라토스테네스의 체로 30000이하의 소수를 찾습니다.
2. 숫자를 하나씩 지워가면서 만들 수 있는 소수 수열을 TOP-DOWN으로 구하면 됩니다.

코드 18줄 ~ 25줄에서 숫자를 지울 때, 그리고 DFS를 할 때 값 설정을 조심해주면 됩니다.
해당 부분은 문자열을 이용해서 숫자를 지우고 DFS를 사용해도 상관 없을 것 같은데, 문제를 푸는 동안 여기가 잘못된 줄 알고 숫자로 변경해서 풀었습니다.

#include <iostream>
#include <cstring>
using namespace std;
using ll = long long;

const int N = 30001;

int t, a, b, score_A, score_B;
ll dp[N], prime[N];

ll go(int x) {
	if (x / 10 == 0) return dp[x] = prime[x];
	ll& ret = dp[x];
	if (ret != -1) return ret;

	if (!prime[x]) return ret = 0;

	ret = 0;
	for (int i = 1; i < x; i *= 10) {
		int na = (x / (i * 10)) * i;
		int nb = x % i;
		int nx = na + nb;

		ret = max(ret, go(nx) + 1);
	}

	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	memset(dp, -1, sizeof(dp));

	for (int i = 0; i < N; i++) prime[i] = 1;

	prime[1] = 0;
	for (int i = 2; i < N; i++) {
		if (prime[i]) {
			for (int j = 2; i * j < N; j++)
				prime[i * j] = 0;
		}
	}
	cin >> t;
	for (int z = 1; z <= t; z++) {
		cin >> a >> b;
		score_A = go(a);
		score_B = go(b);

		cout << "Case #" << z << endl;
		if (score_A > score_B) cout << 1;
		else if (score_A < score_B) cout << 2;
		else cout << 3;
		cout << endl;
	}
}

 

 

3. SCPC 2020 1차 예선 3번 문제 - 사다리 게임 (dp)

문제

 

사다리에는 N개의 세로선이 있는데, 각 세로선은 1~N까지 번호가 있고 (N ≤ 1,500) 가로이음선이 K개 있습니다. (K ≤ 2,000)

쿼리로 a, b 가 주어질 때 a번째 선에서 출발하여 b번째 선으로 나오려면, 최소 몇 개의 가로이음선이 고장나야 하는지 출력하는 문제입니다.

 

풀이

 

* evenharder님의 풀이를 참고하였습니다. (https://evenharder.github.io/algo/scpc-2020-round-1/)

 

문제에서 가로선은 주어진 순서대로 높이가 위에서부터 아래로 구성되기 때문에

N번째 가로선을 이은 사다리의 모양과 정답은 N-1번째 가로선까지 이은 모양과 정답에 의존하게 됩니다.

이 부분에서 dp 풀이를 착안해낼 수 있는데, 더 자세히 설명하자면

 

N번째 가로선이 (a, b) 를 연결하고 있다고 해봅시다. 그렇다면 N번째 가로선까지만 이은 사다리를 놓고 볼 때

 

i번째 세로선에서 a번째 세로선으로 이동할 때 최솟값은 (이후 i -> a 방식으로 표현하겠습니다)

N-1번째 가로선까지만 이은 사다리에서 i -> b 이거나 (여기서 N번째 선이 생기면 b -> a로 이동하면 되므로)

N-1번째 가로선까지만 이은 사다리에서 (i -> a) + 1 이 됩니다. (여기서 N번째 선이 생기면 고장냄)

 

반대로 i번째 세로선에서 b번째 세로선으로 이동할 때 최소값은

N-1번째 가로선까지만 이은 사다리에서 i -> a 이거나 (여기서 N번째 선이 생기면 a -> b로 이동하면 되므로)

N-1번째 가로선까지만 이은 사다리에서 (i -> b) + 1 이 됩니다. (여기서 N번째 선이 생기면 고장냄)

 

i -> a와 i -> b로 가는 길은 위 사례들 밖에 없기 때문에 이 방법으로 1 ~ n까지 i를 수정하면서 계산하면 됩니다.

 

이 방법은 가로 사다리가 k번 주어질 때마다 n번 순회하며 고쳐야 하고, dp[n][n] table의 초기화 과정을 거치기 때문에 시간 복잡도는 대략 O(nk + n^2) 정도 걸립니다.

 

 

소스 코드(.cpp)

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

typedef long long ll;

int dp[1501][1501]; //dp[i][j] : i -> j 로 가는 길에서 고장내야하는 최소 이음선 개수

int main(int argc, char** argv)
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	int cnt = 0;
	while (t--) {
	    cnt++;
		int n, k, m;
		cin >> n >> k >> m;

		//inf 값으로 모두 초기화
		memset(dp, 125, sizeof(dp));
		int INF = dp[0][0];

		//시작 - 도착이 같은 지점들 0으로 초기화
		for (int i = 1; i <= n; i++) dp[i][i] = 0;

		for (int i = 0; i < k; i++) {
			int a, b; cin >> a >> b;

			// a - b 가 연결 될 때 어떻게 될까?
			for (int j = 1; j <= n; j++) {
				//j - a = (이전 높이 때의) j -> b 면 a-b가 생겼으니 꽁짜, j->a면 피해야하므로 +1
				int ans1 = min(dp[j][b], dp[j][a] + 1);
				//j - b 위와 동일
				int ans2 = min(dp[j][a], dp[j][b] + 1);
				
				//중간에 계산 결과가 바뀔 수 있으므로 모두 계산 후 저장
				dp[j][a] = ans1; dp[j][b] = ans2;
			}
		}

		int ans = 0;

		for (int i = 0; i < m; i++) {
			int a, b; cin >> a >> b;
			ans += (dp[a][b] >= INF) ? -1 : dp[a][b];
		}
		cout<<"Case "<<"#"<<cnt<<"\n";
		cout << ans << "\n";
	}

	return 0;
}