[BOJ 15477 // C++] 水ようかん (Mizuyokan)

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

 

이번에 볼 문제는 백준 15477번 문제인 水ようかん (Mizuyokan)이다.
문제는 아래 링크를 확인하자.

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

15477번: 水ようかん (Mizuyokan)

양갱을 토막냈을 때 가장 짧은 길이의 양갱은 항상 존재할 수밖에 없고, 그 길이의 후보는 많아야 N*(N-1)/2가지임을 알 수 있다.

 

가장 짧은 길이의 후보를 한번씩 정한 뒤, 각 길이에 대하여 구간DP를 이용해 각 경우의 답을 구해 그중 최솟값을 출력하는 것으로 문제를 해결하자. 단, 그 길이의 양갱이 실제로 존재하는지 등에 대한 예외처리에 유의하자.

 

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

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

int N;
int arr[51];
int psum[51];

vector<int> vec;
int ans = 1000000007;

int dp[51][51];
int visited[51][51];

int func(int L, int R, int& x) {
	if (visited[L][R]) return dp[L][R];
	visited[L][R] = 1;
	int& ret = dp[L][R];

	if (L == R) return ret = 0;
	
	for (int k = L + 1; k <= R; k++) {
		int tmp = psum[k] - psum[L];
		if (tmp < x) continue;
		ret = min(ret, max(tmp - x, func(k, R, x)));
		if ((tmp == x && visited[k][R] < 3) || visited[k][R] == 2) visited[L][R] = 2;
	}

	if (dp[L][R] == 1000000007) visited[L][R] = 3;

	return ret;
}

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

	cin >> N;
	for (int i = 1; i <= N; i++) cin >> arr[i];
	for (int i = 1; i <= N; i++) psum[i] = psum[i - 1] + arr[i];

	for (int i = 0; i <= N; i++) {
		for (int j = i + 1; j <= N; j++) vec.emplace_back(psum[j] - psum[i]);
	}

	sort(vec.begin(), vec.end());
	vec.pop_back();

	for (auto& x : vec) {
		memset(visited, 0, sizeof(visited));
		for (int i = 0; i <= N; i++) {
			for (int j = 0; j <= N; j++) {
				dp[i][j] = 1000000007;
			}
		}

		int tmp = func(0, N, x);
		if (visited[0][N] == 2) ans = min(ans, tmp);
	}

	cout << ans;
}