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

링크

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

문제

꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이는 오른쪽으로 i 초 기어가야 도달할 수 있다. 또한 매초 1 만큼 오른쪽으로 무조건 진행한다.

호석 애벌레는 i 번째 먹이가 맛있을수록 높은 만족도를 얻는다. 호석 애벌레는 절제라는 것을 모르는 욕심쟁이기 때문에 한번 먹이를 먹기 시작하면 연속적으로 계속 먹어야 하며, 누적된 만족도가 최소 만족도 K  이상이 되거나 더 이상 먹을 먹이가 없을 때에 연속적으로 먹는 것을 멈춘다. 만약 최소 만족도 이상이 되면 K 를 초과한 만족도만큼 탈피 에너지를 축적한다. 직후에 호석 애벌레의 만족도는 다시 0 이 되고 먹이를 먹을 수 있게 된다. 나뭇가지를 전부 통과했을 때에 소화를 다 못 했을 경우에도 탈피 에너지는 최소 만족도를 넘기는 순간 이미 축적한 것으로 생각하자.

예를 들어 위와 같이 9개의 먹이가 존재하면, 호석 애벌레는 미래를 도모하여 1번 먹이를 과감하게 포기한다. 그리고 2번부터 먹기 시작해서 3번까지 먹으면 만족도가 9가 되어 3의 에너지를 축적하게 된다. 같은 이유로 4번 먹이도 포기하고 5번부터 먹으면 7번까지 연속으로 먹어서 15의 만족도를 얻는다. 이를 통해 9의 탈피 에너지가 쌓인다. 8, 9번 먹이까지 먹게 되면 2의 탈피 에너지가 축적된다. 이렇게 얻은 총 14의 탈피 에너지가 위의 예제에서는 최대치이다.

매초마다 호석 애벌레는 오른쪽으로 이동하면서 먹이를 지나치거나 먹기 시작할 수 있다. 먹기 시작하면 만족도가 채워질때까지 먹게 될것이다. 어떤 먹이들을 대해 먹어야 축적된 탈피 에너지가 최대가 될 수 있을까?

입력

첫번째 줄에 먹이 개수 N, 최소 만족도 K 가 공백으로 주어진다.

두번째 줄에는 1 번부터 N 번 먹이의 만족도가 순서대로 주어진다.

출력

축적된 탈피 에너지의 최댓값을 구하라. 만약 탈피를 한 번도 할 수 없다면 0을 출력한다.

나의 풀이

• 참고 코드 : https://blog.naver.com/PostView.nhn?blogId=adamdoha&logNo=222147929582&categoryNo=67&parentCategoryNo=0&viewDate=¤tPage=1&postListTopCurrentPage=1&from=search
• 어떻게 풀이해도 틀려서 결국 다른 사람의 코드를 참고했다. dp에 최대 누적합을 갱신해주는 형태이다.
  • i,j 투포인터로 energy전체를 순회하며, 최대인 값을 뽑아낸다.
  • sum이 K이상일 때까지 더해주고, 그때, i이전까지의 누적합 최대와 i부터j까지의 합을 더해서, 기존 dp[j]에 위치한 값과 비교하여 더 큰 값으로 dp[j]를 갱신한다.
  • i를 한칸 오른쪽으로 움직이면서 sum도 기존 energy[i]를 빼주고, prev_max도 갱신해준다.
• 핵심 코드

  for (int i = 0; i < N; i++) {
              while(j+1<N&&sum<K){
                  sum+=energy[++j];
              }
              dp[j]=Math.max(dp[j],prev_max+Math.max(0,sum-K));
              sum-=energy[i];
              prev_max=Math.max(prev_max,dp[i]);
          }

• 전체 코드

  package Baekjoon.java.gold;
  
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.Arrays;
  import java.util.StringTokenizer;
  
  //참고 코드 : https://blog.naver.com/PostView.nhn?blogId=adamdoha&logNo=222147929582&categoryNo=67&parentCategoryNo=0&viewDate=&currentPage=1&postListTopCurrentPage=1&from=search
  public class boj20181 {
      public static void main(String[] args) throws Exception{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer(br.readLine());
          int answer = 0;
          int N = Integer.parseInt(st.nextToken());
          int K = Integer.parseInt(st.nextToken());
          st = new StringTokenizer(br.readLine());
          long [] energy = new long[N];
          long []dp = new long[N];
          for (int i = 0; i < N; i++) {
              energy[i] = Long.parseLong(st.nextToken());
          }
  
          long sum=0;
          long prev_max = 0;
          int j = -1;
          for (int i = 0; i < N; i++) {
              while(j+1<N&&sum<K){
                  sum+=energy[++j];
              }
              dp[j]=Math.max(dp[j],prev_max+Math.max(0,sum-K));
              sum-=energy[i];
              prev_max=Math.max(prev_max,dp[i]);
          }
  
          System.out.println(prev_max);
      }
  }

결과