[알고리즘] 최대점수 구하기(DFS)

ho's·2022년 7월 13일
0

DFS

목록 보기
1/1

최대점수 구하기

👔 문제

👖 풀이

예제 입력을 보자

DFS 메소드

public void DFS(int L, int sum, int time, int[] ps, int[] pt){
	if(time>m) return;
    if(L == n){
    	answer = Math.max(answer, sum);
    }
    else{
    	DFS(L+1, sum+ps[L], time+pt[L] ,ps ,pt);
        DFS(L+1, sum, time, ps,pt);
    }	
}

🧦 소스코드

public class Main14{
	static int answer = Integer.MIN_VALUE;
    static int n,m;
    
    public void DFS(int L, int sum, int time, int[] ps, int[] pt){
    	if(time>m)
        	return;
        if(L == n){
        	answer = Math.max(answer, sum);
        }
        else{
        	DFS(L+1, sum+ps[L], time+pt[L], ps,pt);
            
        }
        
    
    }

	public static void main(String[] args){
    	Main14 T = new Main14();
        
        Scanner scan = new Scanner(System.in);
        
        n = scan.nextInt();
        m = scan.nextInt();
        
        int[] a = new int[n];
        int[] b = new int[n];
        
        for(int i=0;i<n;i++){
        	a[i] = scan.nextInt();
            b[i] = scan.nextInt();
        }
        T.DFS(0, 0, 0, a, b);
        System.out.println(answer);
    }
}
profile
그래야만 한다

0개의 댓글