[Ch.08 - DFS] 05. 최대점수 구하기

3. 최대점수 구하기(DFS)

-> 냅색 알고리즘으로 풀기

https://and-some.tistory.com/663

[Ch.10 - DP] 06. 최대점수 구하기 [+냅색 알고리즘]

 

설명

이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다.

각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다.

제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다.

(해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)

입력

첫 번째 줄에 문제의 개수N(1<=N<=20)과 제한 시간 M(10<=M<=300)이 주어집니다.

두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.

출력

첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다.

예시 입력 1 

5 20
10 5
25 12
15 8
6 3
7 4

예시 출력 1

41

---

문제 풀이 순서

1. DFS -> O,X로 나눈다
2. 최고 점수를 찾기위한 if문 설정 -> 제한시간 M안에 N개의 문제를 푼다.
   1. 제한 시간, 문제 개수 체크
      • L>n || tsum>m보다 크면 false
   2. 조건 충족 확인
      • L==n || tsum==m이면 Max값 리턴
   3. 그외엔 깊이탐색
      • DFS(L+1, qsum+arr[L][0],tsum+arr[L][1],arr);
      • DFS(L+1, qsum,tsum, arr);

 

---

 

import java.util.Scanner;
//최대점수 구하기 (DFS)
//제한시간 M
//N개의 문제
//얻을 수 있는 최대점수를 출력

class Main {
	static int n , m, answer;
	
	public void DFS(int L, int qsum, int tsum,int[][] arr) {
		if(L>n ||tsum>m) {
			return;
		}
		if(L==n || tsum==m) {
			answer=Math.max(answer, qsum);
		}
		else {
			DFS(L+1, qsum+arr[L][0],tsum+arr[L][1],arr);
			
			DFS(L+1, qsum,tsum, arr);
		}
	}
	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		m = kb.nextInt();
		int [][] arr= new int[n][2];
		for(int i=0; i<n;i++) {
			for(int j=0;j<2;j++) {
			arr[i][j]=kb.nextInt();
			}
		}
		T.DFS(0,0,0,arr);
		System.out.println(answer);
	}
}

 

+) arr를 전역변수로

import java.util.*;
  
public class Main{
  static int n,m, answer=Integer.MIN_VALUE;
  static int[][] arr;
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    n = in.nextInt();
    m = in.nextInt();
    arr = new int[n][2];
    for(int i=0;i<n;i++){
      for(int j=0;j<2;j++){
        arr[i][j]=in.nextInt();
      }
    }
    DFS(0, 0, 0);
    System.out.println(answer);
  }
  static void DFS(int L, int sum, int t){
	if(L<=n && t<=m) {
         answer=Math.max(sum, answer);
	}
    if(L==n || t==m) {
      return;
    }
    else{
      DFS(L+1, sum+arr[L][0], t+arr[L][1]);
      DFS(L+1, sum, t);
    }
    
  }
}

 

 

(1) 얻은 점수, 사용한 시간, 대상 배열

(2) 풀이 시간이 초과 되었을 경우 반환

(3) 풀이시간은 초과되지 않았지만, 문제 수는 최대로 풀었을 경우 -> 지금까지 푼 점수 결과에 넣기

(4) 그 외, DFS 돌기 -> 문제 풀었을 경우, 문제를 못 풀었을 경우

import java.util.Scanner;
  
public class Main {
  static int answer,n,m;
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    n = in.nextInt();
    m = in.nextInt();
    int[][] arr = new int[n][2];
    for(int i=0;i<n;i++){
      for(int j=0;j<2;j++){
      	arr[i][j]=in.nextInt();
        }
    }
    DFS(0,0,0, arr);
    System.out.println(answer);
  }
  static void DFS(int L, int T,int sum, int[][] arr){
    //문제 개수, 문제 풀이 시간, 합계
    //점수와 풀이 시간
    
    //문제 풀이 시간이 초과했을 경우, 문제를 다 풀었을 경우
    if(T>m){
      return;
    }
    if(L==n){
      answer=Math.max(sum, answer);
      return;
    }
    else{
    	DFS(L+1, T+arr[L][1], sum+arr[L][0], arr);
    	DFS(L+1, T, sum, arr);
    }
  }
}