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

woon_12 3년 전 0

이 문제 관련 반례, 랜덤 반례 돌려봐도 모르겠네요.

import java.util.Scanner;

public class Qnum14501 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int roof = sc.nextInt();
		int max = 0;
		int[] dp = new int[roof+1];
		for(int i=0; i<roof; i++) {
			int t = sc.nextInt();
			int p = sc.nextInt();
			
			if(i+t>roof)
				continue;
			
			dp[i+t] = Math.max(
					Math.max(dp[i+t], dp[i]+p),
					dp[Math.max(0, i-1)]+p);
			
			max = Math.max(dp[i+t], max);
			
		}
		
		System.out.println(max);
		sc.close();
	}
}

adfsfsf 3년 전 0

예제를 살짝 바꿔보았습니다.

3 10

5 20

1 10

2 20

4 15

2 10

2 200

이 경우, 6번째 원소를 조사할 때 dp[5]가 0이고, dp[4]가 0이므로 dp[7]이 10이 됩니다. 하지만 실제 dp[7]의 실제 값은 40입니다.

위 결과는 dp를 초기화 했을 때의 결과이며, 메인 클래스의 이름은 Main이 되어야 합니다.

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

문제

문제

출처

ICPC

반례가 있을까요.

woon_12 3년 전 0

adfsfsf 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말