[백준] 20167, 20181 꿈틀 꿈틀 호석 애벌레

[백준] 20167, 20181 꿈틀 꿈틀 호석 애벌레

참고: https://www.acmicpc.net/problem/20167, https://www.acmicpc.net/problem/20181

꿈틀꿈틀 호석 애벌레 - 기능성

문제에 주어진 조건이 크지 않으므로 브루트 포스로 해결할 수 있다. 애벌레가 먹이를 먹는 경우와 그렇지 않은 경우로 나눌 수 있고, 만족도가 K 이상일 때 만족도를 0 으로 하고 탈피 에너지를 증가하면 해결할 수 있다.

꿈틀꿈틀 호석 애벌레 - 효율성

동일한 문제로 제한 조건만 달라졌다. 먹이의 개수가 100,000개이며 만족도가 10^8 까지 가능하다. 따라서 브루트 포스로 해결할 수 없다.

일단 특정 구간에서의 누적된 만족도를 구해야하므로 투 포인터(left, right)를 사용하여 누적합을 구할 수 있을 것 같다.

그리고 해당 먹이를 먹는 경우와 그렇지 않응 경우로 나뉘고, 특정 구간에서의 최대 탈피 에너지를 기억해야 하므로 DP를 사용한다.

dp[i] = i 까지의 최대 탈피 에너지

풀이

N = 9, K = 6, 먹이 = [1, 5, 4, 4, 2, 3, 10, 3, 5] 가 주어졌을 때 풀이는 다음과 같다.

0 ~ 1 구간의 누적 만족도는 6으로 탈피 에너지 = 누적 만족도 - K = 0 이다.

0 - 1 구간의 만족도가 6 이상이므로 left를 한 칸 이동 시킨다.

1 - 1 구간의 만족도가 6 미만이므로 right를 한 칸 이동하여 먹이를 먹는다.

1 - 2 구간의 만족도가 9 가 되어 탈피 에너지는 3이 된다.

1 - 2 구간의 만족도가 6 이상이므로 left를 한 칸 이동 시킨다.

2 - 2 구간의 만족도가 6 미만이므로 right를 한 칸 이동하여 먹이를 먹는다.

2 - 3 구간의 만족도가 9 가 되어 탈피 에너지는 2가 된다. 하지만 1 - 2 구간과 2 - 3 구간에서 2번 먹이가 겹치므로 두 구간 중 탈피 에너지가 더 큰 1 - 2 구간을 선택한다. 따라서 dp[3] = 3이 된다.

현재까지 상황은 위와 같다. 이렇게 left, right를 이동하면서 최대 탈피 에너지를 구할 수 있다.

꿈틀꿈틀 호석 애벌레 - 기능성

import java.io.*; import java.util.StringTokenizer; public class Main { static int N, K, result = 0; static int[] arr; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); K = Integer.parseInt(st.nextToken()); arr = new int[N]; st = new StringTokenizer(br.readLine()); for (int i=0;i= K) { dfs(idx + 1, 0, energy + satisfaction + arr[idx] - K); } else { dfs(idx + 1, satisfaction + arr[idx], energy); } } }

꿈틀꿈틀 호석 애벌레 - 효율성

import java.io.*; import java.util.*; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int K = Integer.parseInt(st.nextToken()); int[] arr = new int[N]; st = new StringTokenizer(br.readLine()); for (int i=0;i= K) { while (sum >= K) { dp[right] = Math.max(dp[right], dp[left] + sum - K); sum -= arr[left++]; } } else { dp[right] = Math.max(dp[right], dp[right - 1]); if (right == N) break; sum += arr[right++]; } } System.out.println(dp[N]); } }

from sys import stdin from collections import defaultdict readline = stdin.readline N, K = map(int, readline().split()) arr = list(map(int, readline().split())) dp = defaultdict(int) def solve(): left, right, _sum = 0, 0, 0 while right <= N: if _sum >= K: while _sum >= K: dp[right] = max(dp[right], dp[left] + _sum - K) _sum -= arr[left] left += 1 else: dp[right] = max(dp[right], dp[right - 1]) if right == N: break _sum += arr[right] right += 1 print(dp[N]) solve()

728x90

from http://white-board.tistory.com/192 by ccl(A) rewrite - 2021-10-06 09:01:37