글 읽기 - 게시판에 있는 반례들 다 해봤는데 70%에서 틀렸다고 나옵니다.

hy10128 4년 전 0

10
1 2 0 1 3 2 1 5 4 2

일때

배열의 자리수 + 배열 값이 N 이상일 경우 저장된 dp값을 ans에 저장한뒤

ans+1이 답이되게 만들었습니다.

게시판에 있는 반례들을 보면서

if문으로 예외값을 뒀구요. 자체적으로도 반례 만들어서 돌려보는데 못찾겠습니다..

import java.util.*;
import java.io.*;

public class Main {
	static int N;
	static int[] arr;
	static int[] dp;
	static int ans=0;
	static boolean chk=false;
	public static void dfs(int cur)
	{
		if(cur==N)
		{
			chk=true;
			return;
		}
		int jump = arr[cur-1];
		for(int i=cur;jump>0;i++)
		{
			
			dp[i]=Math.min(dp[i],dp[cur-1]+1);
			jump--;
		}
		if(cur+arr[cur]>=N)
		{
			ans = dp[cur];
			return;
		}
		dfs(cur+1);
	}
	public static void main(String[] args) throws IOException {
    	
    	BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] input = bf.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        input = bf.readLine().split(" ");
        arr = new int[N+1];
        int max=0;
        for(int i=1;i<=N;i++)
        {
        	arr[i] = Integer.parseInt(input[i-1]);
        	if(max<arr[i])
        		max=arr[i];
        }
        dp = new int[N+1];
        
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[1]=0;
        dfs(1);
//        for(int i=1;i<=N;i++)
//        	System.out.print(dp[i]+" ");
//        System.out.println();
//        System.out.println(Integer.MAX_VALUE);
        if(N==1)
        	System.out.print(0);
        else if(chk==true || ans==Integer.MAX_VALUE || arr[1]==0)
        	System.out.println(-1);
        else
        System.out.println(ans+1);
	}
} 

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

문제

문제

출처

ICPC

게시판에 있는 반례들 다 해봤는데 70%에서 틀렸다고 나옵니다.

hy10128 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말