※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 3299번 문제인 POWER이다.
문제는 아래 링크를 확인하자.

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

 

3299번: POWER

First line of the input file contains integer N, 2 ≤ N ≤ 1000, the number of lamps in the village. Second line contains integer V, 1 ≤ V ≤ N, number of the lamp at which Dobrica started. Each of the following N lines contains data describing a lamp

www.acmicpc.net

dp[L][R][dir]을 "구간 [L,R]에 모든 번호의 램프가 꺼질 때까지의 (구간 내에 포함되지 않은 램프를 포함한 모든 램프의) 에너지 소비량의 최솟값"으로 정의하자. (단, [L,R]이 V를 포함할 때에만 정의된다.) dir은 모든 램프를 끈 뒤 가로등 L에 위치하는지 R에 위치하는지를 나타내는 변수이다. ([L,R]의 모든 램프를 에너지 소비를 최소화하며 끄는 것을 마치면 항상 L 또는 R에서 작업을 마무리함을 관찰하자.)

 

이 때, dp[L][R][0]은 dp[L+1][R][0]에서 (L+1번 램프의 위치에서 L번 램프까지 이동하는 동안 소비된 에너지의 양), 즉 (L+1번 램프와 L번 램프 사이 거리) * ([L+1,R]에 포함되지 않는 램프의 개수)을 더한 값과 dp[L+1][R][1]에서 (R번 램프의 위치에서 L번 램프까지 이동하는 동안 소비된 에너지의 양), 즉 (R번 램프와 L번 램프 사이 거리) * ([L+1,R]에 포함되지 않는 램프의 개수)를 더한 값 둘 중 작은 값이 된다. 이와 같은 방식으로 dp[L][R][1]에 대한 식 또한 얻을 수 있다.

 

각 [L,R] 구간에 대한 계산은 해당 구간이 포함하는 더 작은 크기의 구간에 대한 값만을 이용해 계산하므로 위와 같은 점화관계를 통해 문제를 충분히 해결할 수 있음을 관찰할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int N, V;
ll dp[1001][1001][2];
ll dist[1001], watt[1001];
ll psum[1001];

ll func(int L, int R, int dir) {
	if (dp[L][R][dir]) return dp[L][R][dir];

	ll& ret = dp[L][R][dir] = 1000000007;
	if (dir == 1 && R > V) {
		ret = min(ret, func(L, R - 1, 0) + (dist[R] - dist[L]) * (psum[L - 1] + psum[N] - psum[R - 1]));
		ret = min(ret, func(L, R - 1, 1) + (dist[R] - dist[R - 1]) * (psum[L - 1] + psum[N] - psum[R - 1]));
	}
	else if (dir == 0 && L < V) {
		ret = min(ret, func(L + 1, R, 0) + (dist[L + 1] - dist[L]) * (psum[L] + psum[N] - psum[R]));
		ret = min(ret, func(L + 1, R, 1) + (dist[R] - dist[L]) * (psum[L] + psum[N] - psum[R]));
	}

	return ret;
}

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

	cin >> N >> V;
	for (int i = 1; i <= N; i++) {
		cin >> dist[i] >> watt[i];
		psum[i] = psum[i - 1] + watt[i];
	}

	dp[V][V][0] = dp[V][V][1] = 1;
	cout << min(func(1, N, 0), func(1, N, 1)) - 1;
}
728x90

'BOJ' 카테고리의 다른 글

[BOJ 27285 // C++] L-Board  (0) 2023.09.06
[BOJ 3288 // C++] BEER  (1) 2023.09.05
[BOJ 3298 // C++] WEDDING  (1) 2023.09.03
[BOJ 3286 // C++] SHELVES  (0) 2023.09.02
[BOJ 3287 // C++] CALC  (0) 2023.09.01
취미로 코딩하기measurezero 님의 블로그입니다.

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 3298번 문제인 WEDDING이다.
문제는 아래 링크를 확인하자.

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

 

3298번: WEDDING

In the first line of the input file are two integers N and K, divided by a comma, 1 ≤ N ≤ 10000, 1 ≤ K ≤ 1000, K ≤ N, the total number of people on the wedding and the number of people from Mirko's family. In the next N lines are an integer V, 10

www.acmicpc.net

두 인접한 사람들의 키의 차들의 총합이 가장 작아지게끔 Mirko의 가족 K명의 사이사이(맨 앞과 맨 뒤 포함)에 다른 N-K명을 적절히 집어넣는 문제이다.

 

Mirko의 가족의 키의 최댓값을 kmx, 최솟값을 kmn이라 하자. 이 때 Mirko의 가족이 아니고 키가 kmn과 kmx 사이인 사람은 인접한 두 가족의 키 사이에 들어가는 구간에 (순서에 맞춰) 들어가는 식으로 줄을 서야 함을 쉽게 관찰할 수 있다.

 

이 문제를 어렵게 하는 것은 Mirko의 가족이 아닌 사람 중 키가 kmx보다 크거나 kmn보다 작은 사람들을 넣는 과정이다. 단순하게 생각하면 키가 kmx인 Mirko의 가족 주변에 키가 kmx보다 큰 사람들을 적절한 순서로 넣고 키가 kmn인 Mirko의 가족 주변에 키가 kmn보다 작은 사람들을 적절한 순서로 넣으면 문제를 해결할 수 있어보인다. 하지만 이러한 방식의 배치로는 다음과 같은 케이스를 통과하지 못한다.

Mirko의 가족들: [1500, 1600, 1400, 1500]
추가로 들어갈 사람들: 1000, 2000

이와 같은 케이스에서는 키가 2000인 사람이 키가 1600인 사람의 주변에 들어가는 것 보다는 줄의 한쪽 끝에 서는 것이 이득임을 관찰할 수 있다. 키가 1000인 사람이 키가 1500인 사람의 주변에 들어가는 것 보다는 줄의 다른 한쪽 끝에 서는 것이 이득임 또한 관찰할 수 있다.

 

이와 같은 관찰을 포함하면, 키가 kmx보다 큰 사람들 또는 kmn보다 작은 사람들이 줄을 서야하는 위치의 경우들을 아래와 같이 7가지로 분류할 수 있다.

 

1) 키가 kmx보다 큰 사람들은 맨 왼쪽에, kmn보다 작은 사람들은 키가 kmn인 Mirko 가족 주변에

2) 키가 kmx보다 큰 사람들은 맨 왼쪽에, kmn보다 작은 사람들은 맨 오른쪽에

3) 키가 kmx보다 큰 사람들은 키가 kmx인 Mirko 가족 주변에, kmn보다 작은 사람들은 맨 왼쪽에

3) 키가 kmx보다 큰 사람들은 키가 kmx인 Mirko 가족 주변에, kmn보다 작은 사람들은 맨 오른쪽에

5) 키가 kmx보다 큰 사람들은 맨 오른쪽에, kmn보다 작은 사람들은 맨 왼쪽에

6) 키가 kmx보다 큰 사람들은 맨 오른쪽에, kmn보다 작은 사람들은 키가 kmn인 Mirko 가족 주변에

7) 키가 kmx보다 큰 사람들은 키가 kmx인 Mirko 가족 주변에, kmn보다 작은 사람들은 키가 kmn인 Mirko 가족 주변에

 

키가 kmx보다 큰 사람과 키가 kmn보다 작은 사람 모두를 왼쪽에 또는 모두를 오른쪽에 몰아넣을 경우는 존재하지 않음을 확인하자.

 

위의 각 경우별로 문제를 해결해주자.

 

아래는 제출한 소스코드이다.

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

int N, K;
int arr[10002];
int lentosg[2201];
vector<int> sg[10002];

int kfirst, klast, kmx, kmn, nmx, nmn = 1000000007;
int total;

int mxL, mxM, mxR, mnL, mnM, mnR;

bool comp(int& x, int& y) {
	return arr[x] < arr[y];
}

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

	cin >> N >> K;

	cin >> arr[1];
	int old = arr[1];

	kmx = kmn = old;

	for (int id = 2; id <= K; id++) {
		int& cur = arr[id]; cin >> cur;
		kmx = max(kmx, cur), kmn = min(kmn, cur);
		total += abs(cur - old);

		if (old < cur) {
			for (int i = old; i <= cur; i++) lentosg[i] = id;
		}
		else {
			for (int i = cur; i <= old; i++) lentosg[i] = id;
		}
		old = cur;
	}
	kfirst = arr[1], klast = arr[K];

	for (int i = 1000; i < kmn; i++) lentosg[i] = 0;
	for (int i = kmx + 1; i < 2201; i++) lentosg[i] = 10001;

	for (int id = K + 1; id <= N; id++) {
		int& cur = arr[id]; cin >> cur;
		nmx = max(nmx, cur), nmn = min(nmn, cur);
		sg[lentosg[cur]].emplace_back(id);
	}

	if (nmx > kmx) mxL = nmx - kfirst, mxM = (nmx - kmx) * 2, mxR = nmx - klast;
	if (nmn < kmn) mnL = kfirst - nmn, mnM = (kmn - nmn) * 2, mnR = klast - nmn;

	if (mxL <= min(mxM, mxR) && mnM <= min(mnL, mnR)) {
		cout << total + mxL + mnM << '\n';

		sort(sg[10001].begin(), sg[10001].end(), comp);
		for (auto iter = sg[10001].rbegin(); iter != sg[10001].rend(); iter++) cout << *iter << '\n';

		cout << 1 << '\n';
		for (int id = 2; id <= K; id++) {
			if (id == lentosg[kmn]) {
				sort(sg[0].begin(), sg[0].end(), comp);
				for (auto& x : sg[0]) cout << x << '\n';
			}
			sort(sg[id].begin(), sg[id].end(), comp);
			if (arr[id - 1] < arr[id]) {
				for (auto iter = sg[id].begin(); iter != sg[id].end(); iter++) cout << *iter << '\n';
			}
			else {
				for (auto iter = sg[id].rbegin(); iter != sg[id].rend(); iter++) cout << *iter << '\n';
			}

			cout << id << '\n';
		}
	}

	else if (mxL <= min(mxM, mxR) && mnR <= min(mnL, mnM)) {
		cout << total + mxL + mnR << '\n';

		sort(sg[10001].begin(), sg[10001].end(), comp);
		for (auto iter = sg[10001].rbegin(); iter != sg[10001].rend(); iter++) cout << *iter << '\n';

		cout << 1 << '\n';
		for (int id = 2; id <= K; id++) {
			sort(sg[id].begin(), sg[id].end(), comp);
			if (arr[id - 1] < arr[id]) {
				for (auto iter = sg[id].begin(); iter != sg[id].end(); iter++) cout << *iter << '\n';
			}
			else {
				for (auto iter = sg[id].rbegin(); iter != sg[id].rend(); iter++) cout << *iter << '\n';
			}

			cout << id << '\n';
		}

		sort(sg[0].begin(), sg[0].end(), comp);
		for (auto iter = sg[0].rbegin(); iter != sg[0].rend(); iter++) cout << *iter << '\n';
	}
	else if (mxM <= min(mxL, mxR) && mnL <= min(mnM, mnR)) {
		cout << total + mxM + mnL << '\n';

		sort(sg[0].begin(), sg[0].end(), comp);
		for (auto& x : sg[0]) cout << x << '\n';

		cout << 1 << '\n';
		for (int id = 2; id <= K; id++) {
			if (id == lentosg[kmx]) {
				sort(sg[10001].begin(), sg[10001].end(), comp);
				for (auto& x : sg[10001]) cout << x << '\n';
			}
			sort(sg[id].begin(), sg[id].end(), comp);
			if (arr[id - 1] < arr[id]) {
				for (auto iter = sg[id].begin(); iter != sg[id].end(); iter++) cout << *iter << '\n';
			}
			else {
				for (auto iter = sg[id].rbegin(); iter != sg[id].rend(); iter++) cout << *iter << '\n';
			}

			cout << id << '\n';
		}
	}
	else if (mxM <= min(mxL, mxR) && mnR <= min(mnL, mnM)) {
		cout << total + mxM + mnR << '\n';

		cout << 1 << '\n';
		for (int id = 2; id <= K; id++) {
			if (id == lentosg[kmx]) {
				sort(sg[10001].begin(), sg[10001].end(), comp);
				for (auto& x : sg[10001]) cout << x << '\n';
			}
			sort(sg[id].begin(), sg[id].end(), comp);
			if (arr[id - 1] < arr[id]) {
				for (auto iter = sg[id].begin(); iter != sg[id].end(); iter++) cout << *iter << '\n';
			}
			else {
				for (auto iter = sg[id].rbegin(); iter != sg[id].rend(); iter++) cout << *iter << '\n';
			}

			cout << id << '\n';
		}

		sort(sg[0].begin(), sg[0].end(), comp);
		for (auto iter = sg[0].rbegin(); iter != sg[0].rend(); iter++) cout << *iter << '\n';
	}
	else if (mxR <= min(mxL, mxM) && mnL <= min(mnM, mnR)) {
		cout << total + mxR + mnL << '\n';

		sort(sg[0].begin(), sg[0].end(), comp);
		for (auto& x : sg[0]) cout << x << '\n';

		cout << 1 << '\n';
		for (int id = 2; id <= K; id++) {
			sort(sg[id].begin(), sg[id].end(), comp);
			if (arr[id - 1] < arr[id]) {
				for (auto iter = sg[id].begin(); iter != sg[id].end(); iter++) cout << *iter << '\n';
			}
			else {
				for (auto iter = sg[id].rbegin(); iter != sg[id].rend(); iter++) cout << *iter << '\n';
			}

			cout << id << '\n';
		}
		sort(sg[10001].begin(), sg[10001].end(), comp);
		for (auto& x : sg[10001]) cout << x << '\n';
	}
	else if (mxR <= min(mxL, mxM) && mnM <= min(mnL, mnR)) {
		cout << total + mxR + mnM << '\n';

		cout << 1 << '\n';
		for (int id = 2; id <= K; id++) {
			if (id == lentosg[kmn]) {
				sort(sg[0].begin(), sg[0].end(), comp);
				for (auto& x : sg[0]) cout << x << '\n';
			}
			sort(sg[id].begin(), sg[id].end(), comp);
			if (arr[id - 1] < arr[id]) {
				for (auto iter = sg[id].begin(); iter != sg[id].end(); iter++) cout << *iter << '\n';
			}
			else {
				for (auto iter = sg[id].rbegin(); iter != sg[id].rend(); iter++) cout << *iter << '\n';
			}

			cout << id << '\n';
		}
		sort(sg[10001].begin(), sg[10001].end(), comp);
		for (auto& x : sg[10001]) cout << x << '\n';
	}
	else {
		cout << total + mxM + mnM << '\n';

		cout << 1 << '\n';
		for (int id = 2; id <= K; id++) {
			if (id == lentosg[kmx]) {
				sort(sg[10001].begin(), sg[10001].end(), comp);
				for (auto& x : sg[10001]) cout << x << '\n';
			}
			if (id == lentosg[kmn]) {
				sort(sg[0].begin(), sg[0].end(), comp);
				for (auto& x : sg[0]) cout << x << '\n';
			}
			sort(sg[id].begin(), sg[id].end(), comp);
			if (arr[id - 1] < arr[id]) {
				for (auto iter = sg[id].begin(); iter != sg[id].end(); iter++) cout << *iter << '\n';
			}
			else {
				for (auto iter = sg[id].rbegin(); iter != sg[id].rend(); iter++) cout << *iter << '\n';
			}

			cout << id << '\n';
		}
	}
}
728x90

'BOJ' 카테고리의 다른 글

[BOJ 3288 // C++] BEER  (1) 2023.09.05
[BOJ 3299 // C++] POWER  (0) 2023.09.04
[BOJ 3286 // C++] SHELVES  (0) 2023.09.02
[BOJ 3287 // C++] CALC  (0) 2023.09.01
[BOJ 3285 // C++] DECODE  (0) 2023.08.31
취미로 코딩하기measurezero 님의 블로그입니다.

+ Recent posts

티스토리툴바