글 읽기 - 틀린부분을 모르겠어요. 반례 찾는 것좀 도와주세요

eeww95 5년 전 0

안녕하세요.

질문에 있는 반례도 돌려보고, 예제도 돌려 봤는데 어디서 틀렸는지 모르겠어요 ㅜ

고수님들 반례찾는 것좀 도와 주세요

import java.util.Scanner;

class Work{
	int time;
	int price;
	Work(){}
	Work(int time, int price){this.time = time; this.price = price;}
	public String toString() {return time+ " "+price;}
}

public class Main{
	
	public static int N;
	public static Work[] schedule, total;
	public static Work max;
	public static int location;

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		N = scan.nextInt();
		schedule = new Work[N];
		total = new Work[N];
		max = new Work(0,0);
		location = 0;
		for(int i=0; i<N; i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();
			schedule[i] = new Work(a,b);
			total[i] = new Work();
		} // 입력
		
		for(int i=1; i<=N; i++) {
			findMaxPrice(schedule[N-i],i,i);
		}
		
		System.out.println(total[0].price);
				

	}

	public static void findMaxPrice(Work temp, int index, int remainTime) {
		
		if(N-index+1 <N) { // 배열 0~ N-2
			if(temp.time+total[N-index+1].time<=remainTime && (remainTime - location) >= temp.time) { // 
				if(temp.price+total[N-index+1].price>max.price) {
					max.time = total[N-remainTime].time = temp.time+total[N-index+1].time;
					max.price = total[N-remainTime].price = temp.price + total[N-index+1].price;	
					location = remainTime;
				}
				else {
					total[N-remainTime].time = max.time;
					total[N-remainTime].price = max.price;
					location = remainTime;
				}
			}
			else {
				if(temp.time<=remainTime) { // 시간내 상담이 가능 but 이전꺼랑 같이는 못함
					location--;
					findMaxPrice(temp,index-1, remainTime);
					
				}else { // 시간내 상담이 불가능 하면
					total[N-remainTime].time = max.time;
					total[N-remainTime].price = max.price;
				}
				
			}
		}else { // 배열 N-1
			if(temp.time<=remainTime) { // 상담가능하면
				if(temp.price>max.price) {
				max.time = total[N-remainTime].time = temp.time;
				max.price = total[N-remainTime].price = temp.price;
				}
				else {
					total[N-remainTime].time = max.time;
					total[N-remainTime].price = max.price;
				}
			}else { // 상담불가능 하면
				total[N-remainTime].time = 0;
				total[N-remainTime].price = 0;
			}
		}
		
	}
}

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

문제

문제

출처

ICPC

틀린부분을 모르겠어요. 반례 찾는 것좀 도와주세요

eeww95 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말