[백준 20167, 20181] 꿈틀꿈틀 호석 애벌레 - 기능성, 효율성

문제

www.acmicpc.net/problem/20167

20167번: 꿈틀꿈틀 호석 애벌레 - 기능성

www.acmicpc.net/problem/20181

20181번: 꿈틀꿈틀 호석 애벌레 - 효율성

 

20167 풀이

N의 상한이 20이기에 i번째 먹이를 먹었거나 안 먹었거나를 전부 조사하는 완전 탐색을 통해 2^20에 해결할 수 있습니다.

 

20181 풀이

N의 상한이 크므로 연속된 구간을 관리하기 위해 [l, r)구간을 보는 투 포인터를 사용했습니다. 신경 써야 하는 부분은 i번째 칸까지 탈피 E의 최대 값을 구하는 것과 i번째 칸까지 누적된 만족도를 관리하는 것으로 크게 두 가지가 있고 이는 아래와 같이 해결했습니다.

---

1. i번째까지 탈피E의 최대 값을 구하는 것은 "dp[i] = i번째까지 탈피 E의 최대 값"라고 정의하고 dp배열을 채워나가면 결과적으로 답은 구간[0, n - 1]에서 dp[i]의 최댓 값으로 구할 수 있습니다.

 

2. [l, r)구간의 누적된 만족도는 sum이라는 변수를 통해 관리하고, sum과 k의 대소 비교를 통해 l, r을 조절할 수 있습니다.

   

   1. $ sum >= k $ : [l, r)구간의 누적된 만족도가 k보다 큰 것이므로 l이전까지 탈피 E의 최대 값을 찾아 $sum - k$와 더해 끝점인 dp[r -1] 값을 갱신해주면 되고, l을 한 칸 옮겨 새로운 구간을 찾을 수 있습니다.

   2. $ sum < k $ : [l, r)구간의 누적 만족도가 k보다 작은 것이므로 r을 한 칸 옮깁니다.

20167 코드

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

int n, k, ans;
vector<int> v;

void go(int x, int sum, int e) {
	if (x == n) {
		ans = max(ans, e);
		return;
	}
	go(x + 1, 0, e);
	if (sum + v[x] >= k) go(x + 1, 0, e + sum + v[x] - k);
	else go(x + 1, sum + v[x], e);
}

int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> k;
	v.resize(n);
	for (int &i : v) cin >> i;
	go(0, 0, 0);
	cout << ans;
}

 

20181 코드

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

int n, k, l, r;
ll sum, dp[100001], lmax, ans;
vector<int> v;

int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> k;
	v.resize(n);
	for (int& i : v) cin >> i;
	while (1) {
		if (sum >= k) {
			lmax = (l == 0 ? 0 : max(lmax, dp[l - 1]));
			dp[r - 1] = max(dp[r - 1], lmax + sum - k);
			sum -= v[l++];
		}
		else if (r == n) break;
		else sum += v[r++];
	}
	for (int i = 0; i < n; i++)
		ans = max(ans, dp[i]);
	cout << ans;
}