글 읽기 - 음 틀렸다고 나오는데 어떤케이스일까요..

shin8901 4년 전 0

맨 뒤 cache 부터 채워가면서 cache 1에 가장 최대값을 구하는 형태로 구현해봤는데,

틀렸다고 나옵니다. 몇가지 케이스 만들어서 실행해봤는데 ,, 그 케이스는 답은 또맞고 ㅋㅋ

도와주세요!

>>>>>>>>>>>>>>>>>>>>>> 수정

아 cache 에 대한 내용을 방문이 여러번 가능한 도시를 위해 이차원 배열이 필요했었네요

자체 해결하였습니다.

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

public class Main {
	static int N;
	static int M;
	static int K;

	static int answer = Integer.MIN_VALUE;

	static int[][] map;

	static int[] cache;

	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			N = sc.nextInt(); // N개의 도시
			M = sc.nextInt(); // M개 이하의 도시를 지나야함
			K = sc.nextInt(); // K 개의 항로가 있움

			map = new int[N + 1][N + 1];
			cache = new int[N + 1];

			// 최대치 이외에는 필요없을듯
			for (int i = 0; i < K; i++) {
				int x = sc.nextInt();
				int y = sc.nextInt();
				int value = sc.nextInt();

				map[x][y] = Math.max(value, map[x][y]);
			}

            Arrays.fill(cache, -1);
			int value = dfs(1, 1);
			System.out.println(value);
			//print();

		}

	}

	private static void print() {
		for (int i = 0; i < cache.length; i++) {
			System.out.print(cache[i] + " ");
		}
		System.out.println();
	}

	private static int dfs(int city, int count) {

		// 도달 못했으
		if (count >= M && city != N) {
			//cache[city] = Integer.MIN_VALUE;
			return Integer.MIN_VALUE;
		}

		// N에 도달하믄 뭐 다음으로 갈곳이 없으니
		// 기내식은 0
		if (city == N) {
			cache[city] = 0;
			return 0;
		}

		// 온적없으면
		if (cache[city] == -1) {
			cache[city] = 0;

			for (int i = city + 1 /* 큰 쪽으로만 가면되니까 */ ; i <= N; i++) {
				if (map[city][i] > 0) {
					// 현재 에서 다음으로 가는 기내식이랑
					// 다음 값이랑
					cache[city] = Math.max(cache[city], dfs(i, count + 1) + map[city][i]);
				}
			}
		}
		return cache[city];
	}
}

djm03178 4년 전 1

문제 번호를 적는 칸에 문제 번호를 적어주세요.

shin8901 4년 전 0

아 cache 에 대한 내용을 방문이 여러번 가능한 도시를 위해 이차원 배열이 필요했었네요

자체 해결하였습니다.

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

문제

문제

출처

ICPC

음 틀렸다고 나오는데 어떤케이스일까요..

shin8901 4년 전 0

djm03178 4년 전 1

shin8901 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말