글 읽기 - 1005번 자바 Queue 시간초과 살려주십시오.

ssifood 5년 전 0

안녕하세요.

1005번 Queue로 풀었는데

처음엔, 런타임에러 나서 잡고 현재는 시간초과입니다.

로직은

ret[]배열에 1~W까지의 최대값을 갱신하면서 넣습니다.

1부터 W까지 커지면서 값을 갱신하므로, memoization은 작은 값을 부를때 사용합니다. ( 맞는것 같습니다._) 햐햐

제가 질문 게시판을 다 둘러봤는데요.

다른 시간초과 질문의 답변

우선순위 큐를 쓰세요.?? (이것은 잘 이해가 안되서, 큐에 넣을 것중에 큰 값만 추려서 넣음 )
시작지점이 한군데가 아닐수 있다. (현재 소스로 커버된다고 생각)
시작점부터 종점까지 도달하는 경우의수를 모두구해 합을비교하는것보다 하나의 이동거리만큼 비교해가는 구조로 다시 짜니까 되네요. (잘 모름.)
예를 들어 이 문제에서 DP의 초기값으로 사용해서는 안 되는 값 중 하나는 0입니다. (적용하지 않음.)

이런 식의 충고를 봤습니다.

그래도 잘 모르겠어요. 죄송합니다.

자바충입니다.

package now;

import java.util.*;

public class No1005 {

	static int ret[];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		// System.out.println(T);
		for (int kk = 0; kk < T; kk++) {
			int N = sc.nextInt(); // 건물개수
			// System.out.println(N);
			int K = sc.nextInt(); // 건설규칙
			// System.out.println(K);

			int bTime[] = new int[N + 1];
			ret = new int[N + 1];
			// int bTime[] = new int [N];
			for (int i = 1; i <= N; i++) {
				bTime[i] = sc.nextInt();
				// System.out.println(bTime[i]);
			}
			
			int map[][] = new int[N + 1][N + 1];

			String tmp2 = sc.nextLine();
			// System.out.println(tmp2);

			for (int i = 0; i < K; i++) {
				int before = 0;
				int after = 0;

				for (int j = 0; j < 2; j++) {
					int vval = sc.nextInt();
					if (j == 0) {
						before = vval;
					} else {
						after = vval;
					}
				}
				//처음에 map으로 건설비용 계산하려고 했음.
				map[before][after] = bTime[before] + bTime[after];
			}
			
			int W = sc.nextInt();// 건설해야 하는 건물번혼

			ret[1] = bTime[1];
			for (int z = 2; z <= W; z++) {
				calc(map, z, bTime);
			}
			System.out.println(ret[W]);
		}
		sc.close();

	}// main

	private static void calc(int[][] map, int now, int[] bTime) {
		// TODO Auto-generated method stub
		int tot = 0;
		PriorityQueue<Integer> t = new PriorityQueue<Integer>();
		t.add(now);
		while (!t.isEmpty()) {
			int nnow = t.poll();
			Set<Integer> set = new HashSet<Integer>();

			for (int i = 1; i < map.length; i++) {
				if (map[i][nnow] != 0) {
					if (ret[i] != 0) {
						// System.out.println("들어옴");
						tot = ret[i] + bTime[nnow];
						ret[nnow] = Math.max(tot, ret[nnow]);
						 set.add(i);
						//t.add(i);
					}
				}
			} // for

			int max = 0;
			//우선순위 큐 잘모르는데 따라해봄.?? 쓰면된다고 해서 가장 큰값으로 갱신되는 값들만 큐에 넣음.
			for (Integer val : set) {
				int tmax = max;
				max = Math.max(ret[val], max);
				if (tmax != max) {
					t.add(val);
				}
			}

		}

	}
}

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