글 읽기 - 틀리는 테스트케이스좀용

sksdong1 7년 전 0

아래와 같이 dp로 풀었는데요,

틀리는 테스트 케이스좀 알려주시면 감사하겠습니다.

import java.util.Arrays;
import java.util.Scanner;

class Main{
	
	final int INF = 987654321;
	int n,a,b,arr[],dp[];
	Scanner sc = new Scanner(System.in);
	void main(){
		n = sc.nextInt();
		arr = new int[n+1];
		dp = new int[n+2];
        
		Arrays.fill(dp,-1);
		for(int i=1;i<=n;i++) arr[i] = sc.nextInt();
		a = sc.nextInt();
		b = sc.nextInt();
		int ret = jump(a);
		if(ret==INF) ret = -1;
		System.out.println(ret);
	}
	int jump(int here){
		//here에서 목적지로 가는 최소 점프 횟수
		if(here==b) return 0;
		int ret = dp[here];
		if(ret!=-1) return ret;
		ret = INF;
		int mul=1;
		for(;here+mul*arr[here]<=b;){
			ret = min(ret,jump(here+arr[here]*mul++)+1);
		}
		return dp[here] = ret;
	}
	int min(int a,int b){
		return a>b?b:a;
	}
	public static void main(String[] args) {
		new Main().main();
	}
}

flflds0811 7년 전 5

저도 문제를 잘 못 읽고 생각하여 한번 틀렸네요..;; 점점 위치가 커지는 쪽으로만 갈 수 있는 줄 알았는데;;

문제를 잘 읽어보니 '그 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로' 라고 되어있어

'떨어져 있는 곳' 이기 때문에 위치가 작아지는 쪽 (음수방향) 으로도 이동할 수 있습니다.

sksdong1 7년 전 0

감사합니다

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

문제

문제

출처

ICPC

틀리는 테스트케이스좀용

sksdong1 7년 전 0

flflds0811 7년 전 5

sksdong1 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말