글 읽기 - 퇴사 질문입니다.. dp로 풀었는데..

iolk1001 5년 전 0

dp를 이용해서 역순으로 검사하면서 채워나갔는데요..

어떤 반례가 있을까요.. 자꾸 틀립니다

import java.util.Scanner;

class Main{

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int[][] arr = new int[n+1][2];
		for(int i=0; i<n; i++){
			arr[i][0] = sc.nextInt();
			arr[i][1] = sc.nextInt();
		}
		
		int[] dp = new int[n+1];
		int max = 0;
		for(int i=n-1; i>=0; i--){
			if(dp[i] == 0) dp[i] = dp[i+1];
			if(i + (arr[i][0]) > n) continue;
			dp[i] = dp[i+arr[i][0]] + arr[i][1];
			max = Math.max(dp[i], max);
		}

		System.out.println(max);
	}
}

iolk1001 5년 전 0

Max 연산을 해주는걸 빼먹었었습니다..

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

gggkth 5년 전 1

혹시 역순으로 하신 이유가 있나요?

그리고 dp 배열이 처음에 비어있는 상태로 시작하는데 if(dp[i] == 0) dp[i] = dp[i+1]; 이 코드의 용도도 좀 설명해주실 수 있을까요?

dfs로는 풀었는데 dp로는 감이 잘 안 잡히네요ㅜㅜ

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

문제

문제

출처

ICPC

퇴사 질문입니다.. dp로 풀었는데..

iolk1001 5년 전 0

iolk1001 5년 전 0

gggkth 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말