글 읽기 - 반례 좀 부탁드립니다...도저히 모르겠어요

thddudgns79 3년 전 0

벽돌 크기 기준 내림차순으로 정렬한 다음 무게를 변수로 두고 탑다운 dp로 풀었습니다.

제출하면 틀렸다고 나오는데 코드의 어느 부분을 고쳐야할지 모르겠습니다.

몇 시간동안 쳐다봐도 잘 모르겠어요 도와주시면 감사하겠습니다.

import java.util.*;

class brick implements Comparable<brick> {
	int s;
	int h;
	int w;

	brick(int s, int h, int w) {
		this.s = s;
		this.h = h;
		this.w = w;
	}

	public int compareTo(brick obj) {
		if (this.s < obj.s) {
			return 1;
		} else if (this.s == obj.s) {
			return 0;
		} else {
			return -1;
		}
	}
}

public class Main {
	static int n;
	static brick[] b;
	static int[] dp;
	static int[] next;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		b = new brick[n + 1];
		dp = new int[n + 1];
		next = new int[n + 1];
		
		for (int i = 1; i <= n; i++) {
			int s = sc.nextInt();
			int h = sc.nextInt();
			int w = sc.nextInt();
			b[i] = new brick(s, h, w);
			next[i] = -1;
		}

		for (int i = 0; i <= n; i++)
			dp[i] = -1;
		
		Arrays.sort(b, 1, b.length);

		int ans = 0;
		int start = 0;
		for (int i = 1; i <= n; i++) {
			if (ans < dfs(i) + b[i].h) {
				ans = dfs(i) + b[i].h;
				next[start] = i;
			}
		}

		ArrayList<Integer> g = new ArrayList<Integer>();
		for (int i = start; next[i] != -1; i = next[i])
			g.add(next[i]);

		System.out.println(g.size());
		for (int i = g.size() - 1; i >= 0; i--)
			System.out.println(g.get(i));

	}

	public static int dfs(int p) {
		if (dp[p] != -1)
			return dp[p];

		dp[p] = b[p].h;
		for (int i = p + 1; i <= n; i++) {
			if (b[i].w < b[p].w) {
				if (dp[p] < dfs(i) + b[i].h) {
					dp[p] = dfs(i) + b[i].h;
					next[p] = i;
				}
			}
		}

		return dp[p];

	}

}

mone123123 3년 전 1

제가 dp는 잘 모르지만 테스트하는 과정에서 몇개 데이터를 넣어봤는데요...

입력값 :

3
1 1 1
2 2 2
3 3 3

기댓값 :

결과값 :

2
2
1

이런 식으로 나오네요..

1 1

2 2

를 넣어도 결과값이 이상한 것으로 추정됩니다.

thddudgns79 3년 전 0

아 감사합니다!!! 덕분에 수정해서 맞췄습니다! 감사해용

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

문제

문제

출처

ICPC

반례 좀 부탁드립니다...도저히 모르겠어요

thddudgns79 3년 전 0

mone123123 3년 전 1

thddudgns79 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말