글 읽기 - 반례 부탁드립니다 ..

hansorly 4년 전 0

재귀로 풀려고 했습니다 .

게시판에 있는 반례는 전부 해봤는데 다 제대로 나왔습니다.

9%쯤 진행되다가 '틀렸습니다' 가 떳습니다 .

memory에 각 무게 마다 가치의 최대값이 저장되도록 했고,

무게가 동일하지만 최대값이 되지 않는 값은 return 으로 종료해 더이상 검색하지 않도록 했습니다 .

memory에 저장되어 있는 값(가치) 의 최대값을 출력하도록 했습니다 .

도와주세요 .

import java.util.*;

public class Main {
	
	static int n;
	static int k;
	static int arr[][];
	static int memory[];
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		n=scanner.nextInt();
		k=scanner.nextInt();
		arr=new int[n+1][2];
		memory=new int[k+1];
		for(int i=0;i<n;i++) {
			arr[i][0]=scanner.nextInt();
			arr[i][1]=scanner.nextInt();
		}
		for(int i=0;i<=k;i++) {
			memory[i]=0;
		}
		req(-1,0,0);
		int max=0;
		for(int i=0;i<=k;i++) {
			//System.out.println(memory[i]);
			max=Math.max(memory[i], max);
		}
		System.out.println(max);
		
	}
	static void req(int cnt,int weight,int value) {
		if(weight>k) {
			return;
		}
		if(cnt>=n) {
			return;
		}
		if(memory[weight]>value) {
			return;
		}
		if(memory[weight]<value) {
			memory[weight]=value;
		}
		req(cnt+1,weight+arr[cnt+1][0],value+arr[cnt+1][1]);
		req(cnt+1,weight,value);
		
		
	}
}

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

문제

문제

출처

ICPC

반례 부탁드립니다 ..

hansorly 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말