[백준 1612] 조삼모사 - JAVA

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

 

 

dp[i] = dp[i-1] + 현재 바나나

if (dp[i]  > dp[i-k] + k개 바나나를 c 비용으로 옮기는 비용) prev[i] =  k

 

+ 여기서, 바나나를 k개 옮겼을 때와 하나씩 옮겼을 때 비용이 같은 경우도 걸러짐

(답이 여러 개 존재하면, K개 들고 가는 횟수가 가장 적은 것을 구해야 한다)

 

이후 prev를 N부터 순회하며,

k가 적혀있다면, 왼쪽을 기록하고 k칸 전으로 이동한다.

0이 적혀있다면, 1개 옮긴 것이므로 1칸 전으로 이동한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    StringTokenizer st = new StringTokenizer(br.readLine());
    int K = Integer.parseInt(st.nextToken());
    int C = Integer.parseInt(st.nextToken());

    int[] a = new int[N + 1];
    long[] dp = new long[N + 1];
    int[] prev = new int[N + 1];

    st = new StringTokenizer(br.readLine());
    for (int i = 1; i <= N; i++) {
      a[i] = Integer.parseInt(st.nextToken());
    }

    for (int i = 1; i <= N; i++) {

      dp[i] = dp[i - 1] + a[i];

      if (i >= K && dp[i - K] + C < dp[i]) {
        dp[i] = dp[i - K] + C;
        prev[i] = K;
      }
    }

    List<Integer> pos = new ArrayList<>();
    for (int i = N; i >= 0; ) {
      if (prev[i] != 0) {
        pos.add(i - (K - 1));
        i -= K;
      } else {
        i--;
      }
    }

    StringBuilder sb = new StringBuilder();
    Collections.sort(pos);
    for (int p : pos) {
      sb.append(p).append(" ");
    }

    System.out.println(dp[N]);
    System.out.println(pos.size());
    System.out.println(sb);

  }
}