enekelx1   2년 전

테스트 케이스는 전부 맞고 반례 관련 질문에 들어가서 반례들도 전부 넣어보고 랜덤으로 값을 넣어서 30개 정도 테스트케이스를 확인해 봤는데도 

계속 틀렸다고 하네요 혹시 어디에서 잘못됬는지 짚어주실분 계신가요 ㅠㅠㅠ

enekelx1   2년 전

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);

 }

 }

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