글 읽기 - 반례가 뭐가 있을까요..?

zoonvivor 6년 전 0

예전에 풀어봤다가 다시 풀어봤는데 틀렸습니다.

다른점은 dp[2] 부분이 다르더라구요..

근데 정확히 어떤상황에서 틀리는지 감이 안잡힙니다..

반례좀 알려주실수 있으신가요?

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

import javax.rmi.ssl.SslRMIClientSocketFactory;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		int[] dp = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		if (N > 1)
			dp[0] = arr[0];
		if (N > 2)
			dp[1] = arr[0] + arr[1];

		dp[2] = Math.max(dp[1], dp[0] + arr[2]);

		for (int i = 3; i < N; i++) {
			dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 2] + arr[i], dp[i - 3] + arr[i - 1] + arr[i]));
		}
		System.out.println(dp[N - 1]);

	}
}

djm03178 6년 전 1

https://www.acmicpc.net/board/... 여기에 반례가 있습니다.

zoonvivor 6년 전 0

찾았네요.. 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례가 뭐가 있을까요..?

zoonvivor 6년 전 0

djm03178 6년 전 1

zoonvivor 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말