dp로는 문제를 풀어서 dfs를 대비해서 이와 같이 짰는데 dfs는 되려 틀리니까 당황스러워서요 고수님들 부탁좀 드리겠습니다!! ㅠㅠ
지금 댓글에 코드를 올린 이유는 아무리 해도 제가 전에 짠 dp와 dfs 결과값이 일치하는 거 같은데 어디서 오류가 나는건지 모르겠어서요..
dp는 훠~~~~~~~~~얼씬 못하는데 우연히 점화식이 얻어걸린듯 떠올라서 푼거라 실전에서 이렇게 우연히 생각나는 경우가 거의 없기에
dfs로 다시 짜보는데 하루 넘게 걸려서 계속 짜면서 수정하는데도 계속 틀리니까 힘드네요 ㅠㅠ 선배님들 도와주세요!!!
package dp;
import java.util.Scanner;
public class Main {
static int N;
static int[] dp;
static int[] time;
static int[] pay;
public static void main(String[] args) {
Scanner scr = new Scanner(System.in); int max = 0;
N = scr.nextInt(); dp = new int[N + 1];
time = new int[N + 1];
pay = new int[N + 1];
for (int i = 1; i <= N; i++) {
time[i] = scr.nextInt(); pay[i] = scr.nextInt();
dp[i] = 0;
}
for (int i = 1; i <= N; i++) {
if(i+time[i] > N+1) continue;
dp[i] = Math.max(dp[i], pay[i]);
for (int j = i + time[i]; j <= N; j++) {
if (j + time[j] > N+1)
continue;
else
dp[j] = Math.max(dp[j], dp[i] + pay[j]);
}
}
for(int i = 1;i<=N;i++) {
if(max < dp[i]) max = dp[i];
}
System.out.println(max);
}
}
enekelx1 5년 전
테스트 케이스는 전부 맞고 반례 관련 질문에 들어가서 반례들도 전부 넣어보고 랜덤으로 값을 넣어서 30개 정도 테스트케이스를 확인해 봤는데도
계속 틀렸다고 하네요 혹시 어디에서 잘못됬는지 짚어주실분 계신가요 ㅠㅠㅠ