글 읽기 - 1005번 질문드립니다!!

lastindus 6년 전 0

위상정렬 문제인줄 모르고 풀어서 동일한 결과값이 출력되는데 틀렸다네요,,,,

어느 부분에서 틀린지 모르겠습니다...

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		int[] answer = new int[tc];
		for(int i=0;i<tc;i++){
			int N = sc.nextInt();
			int rule = sc.nextInt();
			int[] time = new int[N];
			for(int j=0;j<N;j++){
				time[j] = sc.nextInt();
			}
			int[][] matrix = new int[N][N];
			for(int j=0;j<rule;j++){
				int start = sc.nextInt();
				int end = sc.nextInt();
				matrix[start-1][end-1] = 1;
			}
			int target = sc.nextInt();
			int[] dp = new int[N];
			answer[i] = solution(i,matrix,time,dp,target);
		}
		for(int i=0;i<tc;i++){
			System.out.println(answer[i]);
		}
		
	}
	
	static int solution(int index,int[][] matrix,int[] time,int[] dp,int target){
		dp[0] = time[0];
		int N = dp.length;
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				if(matrix[i][j] == 1){
					dp[j] = Math.max(dp[j],dp[i] + time[j]);
				}
			}
		}
		return dp[target-1];
	}
}

ho94949 6년 전 1

2중포문으로 dynamic programming문제를 해결하셨는데 dp를 갱신하는 순서가 번호 순서네요

이럴 경우에 3->2->1 순으로 dp배열을 갱신하는 경우에는 2->1이 먼저 갱신되고 그 후에 3->2가 갱신되어 3에 있는 데이터가 1에 propagate(전달?) 되지 않습니다.

위상정렬 문제라는것을 아셨으니, dp배열을 갱신하는 순서를 다시 생각해보시기 바랍니다.

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

문제

문제

출처

ICPC

1005번 질문드립니다!!

lastindus 6년 전 0

ho94949 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말