섹션 8. DFS, BFS 활용 3. 최대점수 구하기

문제

• 이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다.  
• 각  문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다.
• 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다.
• (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)

입력

• 첫 번째 줄에 문제의 개수N(1<=N<=20)과 제한 시간 M(10<=M<=300)이 주어집니다.
• 두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.

출력

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

입출력 예제

---

풀이방식

이번 문제는 재귀함수에 대한 문제이다.

---

재귀함수에 대한 자세한 설명은 아래 글을 참조하길 바랍니다.

섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 1. 재귀함수(스택프레임)

섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 1. 재귀함수(스택프레임)

---

설계과정

이전에 풀었던 부분집합 문제와 거의 비슷하다.

1. 문제 푸는데에 걸린 시간이 제한 시간보다 크면 리턴한다.

2. 모든 레벨에 대해 탐색을 끝냈다면 result 변수와 누적합을 비교해서 최대값을 출력한다.

3. 탐색이 끝나지 않았다면 부분집합에 사용할때에는 DFS(L+1, sum + ps[L], time + pt[L], ps, pt) 을 매개변수로 넣어준다.

4. 부분집합에 사용하지 않을 때에는 DFS(L+1, sum, time, ps, pt) 을 매개변수로 넣어준다.

---

풀이과정

1. 각 변수들을 선언 및 초기화한다.

• result : 결과를 저장할 변수로, Integer.MIN_VALUE 를 통해 최소값으로 초기화한다.
• sum : 문제 점수의 누적합이다.
• A [ ] : 각 점수들을 저장하는 배열이다.
• B[ ] : 각 문제를 푸는 시간들을 저장하는 배열이다.
• L : 레벨
• time : 제한시간
• ps[ ] : 문제의 점수
• pt[ ] : 문제 푸는데에 걸리는 시간

2. DFS 메소드를 작성한다.

 

3. 문제 푸는데에 걸린 시간이 제한 시간보다 크면 리턴한다.

 

4. L과 N이 같다면 result와 sum 중에 최대값을 찾아 result에 저장한다.

• L과 N이 같다면 모든 레벨의 탐색을 끝냈다는 것을 의미한다.

5. L과 N이 다르다면 탐색을 계속해야 한다. 해당 원소가 부분집합에 사용된다면 DFS(L+1, sum + ps[L], time + pt[L], ps, pt) 을 매개변수로 넣어준다.

• 해당 문제가 결과에 포함되는 원소라면 sum에는 문제의 점수를, time에는 문제 푸는데에 걸리는 시간을 누적한다.
• 레벨에는 1을 더해서 다음 레벨을 탐색하도록 한다.

7. 해당 원소가 부분집합에 사용되지 않는다면 DFS(L+1, sum, time, ps, pt) 을 매개변수로 넣어준다.

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.