글 읽기 - 틀린 이유를 잘 모르겠습니다.

kcm0147 3년 전 0

dp부분을 처리하는 코드에서 edge 값을 Map으로 짠거 이외에 별 다른점이 없다고 생각하는데

봐도 봐도 틀린 이유를 잘 모르겠습니다 ..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static List<Map<Integer,Integer>> edgeList;
    static int[][] dp;

    static int N,M,K;
    static final int INF = 98765432;


    public static void main(String[] args) throws IOException {
        init();
        System.out.println(calc(1,1,0));

    }




    public static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N=stoi(st.nextToken());
        M=stoi(st.nextToken());
        K=stoi(st.nextToken());
        edgeList=new ArrayList<>();
        dp=new int[N+1][M+1];

        for(int i=0;i<=N;i++)
            Arrays.fill(dp[i],-1);

        for(int i=0;i<=N;i++){
            edgeList.add(new HashMap<>());
        }

        for(int i=0;i<K;i++){
            st= new StringTokenizer(br.readLine());
            int index1=stoi(st.nextToken());
            int index2=stoi(st.nextToken());
            int Iweight=stoi(st.nextToken());

            if(index1>index2) continue;

            if(edgeList.get(index1).containsKey(index2)){
                int curWeight=edgeList.get(index1).get(index2);

                if(curWeight<Iweight){
                    edgeList.get(index1).replace(index2,Iweight);
                }
            }
            else{
                edgeList.get(index1).put(index2,Iweight);
            }
        }

    }

    public static int calc(int index,int cnt,int value){

        if(index==N) return value;
        if(cnt==M) return -INF;
        if(dp[index][cnt]!=-1) return dp[index][cnt];

        dp[index][cnt]=-INF;

        Iterator<Integer> keys = edgeList.get(index).keySet().iterator();

        while(keys.hasNext()){
            int curKey=keys.next();
            int curValue=edgeList.get(index).get(curKey);
            dp[index][cnt]=Math.max(dp[index][cnt],calc(curKey,cnt+1,value+curValue));
        }

        return dp[index][cnt];

    }



    public static int stoi(String input){
        return Integer.parseInt(input);
    }
}

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

문제

문제

출처

ICPC

틀린 이유를 잘 모르겠습니다.

kcm0147 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말