아이디어

• 갔다가 1번 장소로 돌아오는 시간을 제외하고, 남는 시간 동안 가능한 행복도 합이 높은 두 장소를 왔다갔다 하는 것이 좋다.
  • $i$번째 장소에서 $i+1$번째 장소로 이동했다면 $i+1$번째 장소에서 $i$번째 장소로 되돌아가야 한다.
  • 따라서 이때 얻는 행복도는 반드시 $h_i + h_{i+1}$이 된다. $i \gt 1$이지만 0-base index로 만들기 위해 이를 $p_{i-1}$라 쓰자.
  • 이때 구하는 최댓값을 수식으로 쓰면 $\max_{1 \le i<N}\left(\sum_{j=0}^{i-1}p_j +p_i(\lfloor\frac{T}{2}\rfloor - i)\right)$다. (단, $\lfloor\frac{T}{2}\rfloor > i$)
  • 수열의 부분합을 사용하는 코드가 있으므로 누적합 기법을 사용한다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int N, T;
	static int[] h;
	static long[] p, P;
	static long ans;
	
	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		N = Integer.parseInt(tk.nextToken());
		T = Integer.parseInt(tk.nextToken());
		
		h = new int[N+1];
		tk = new StringTokenizer(rd.readLine());
		for (int i=1; i<=N; i++) {
			h[i] = Integer.parseInt(tk.nextToken());
		}
		
		p = new long[N-1];
		P = new long[N-1];
		
		for (int i=0; i<N-1; i++) p[i] = h[i+2] + h[i+1];
		
		P[0] = p[0];
		for (int i=1; i<N-1; i++) P[i] = P[i-1] + p[i];

		ans = Math.max(0, p[0] * (T/2));
		for (int i=1; i<N-1; i++) {
			if (i > T/2) break;
			ans = Math.max(ans, P[i-1] + p[i] * (T/2 - i));
		}
		
		System.out.println(ans);
	}
}

메모리 및 시간

• 메모리: 29568 KB
• 시간: 352 ms

리뷰

• 두 장소를 왔다갔다 하는 것이 제일 좋다는 것에 확신이 없어 풀지 못했던 문제. 그리디는 감인가? 증명인가?