최대점수 구하기(DFS)
이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 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
문제풀이
import sys
sys.stdin=open("input.txt", "r")
def DFS(L, sum, time): #v는 깊이를 의미한다.
global res
if time > m:
return
if L== n:
if sum > res:
res =sum
print(sum)
else:
DFS(L+1, sum + pv[L], time +pt[L]) #왼쪽 자식(사용한다o)
DFS(L+1, sum, time) #오른쪽 자식(사용 안한다.)
if __name__=="__main__":
n, m=map(int, input().split())
pv=list()
pt=list()
for _ in range(n):
score, time =map(int, input().split())
pv.append(score)
pt.append(time)
res = -2147000000
DFS(0, 0, 0) #DFS의 첫번째 요소는 깊이를 의미하는데, 시작이 0일수도 있고, 1일 수도 있다.
Hint
▶두 변수를 여러 줄로 받는 경우에 각 변수를 리스트로 만들기
▶섹션6의 부분집합구하기와 연관된 문제
▶사용한다. 사용 안한다. 전략을 쓴다.
▶재귀함수의 sum인자에 +α를 하는 경우 재귀함수 호출을 통해 값을 누적한다.
▶L은 깊이를 의미한다. 깊이의 초기값이 0부터 시작할 수도 있고, 1부터 시작할 수도 있다.
▶if문에서 특정 조건의 반대 case를 생각해서, 반대 case를 cutting해 버린다.
'파이썬 알고리즘 > DFS, BFS 활용' 카테고리의 다른 글
6. 알파코드(DFS) (0) | 2022.11.10 |
---|---|
5.동전 분배하기(DFS) (0) | 2022.11.09 |
4. 동전바뀌주기 (0) | 2022.11.09 |
3. 양팔저울(DFS) (0) | 2022.11.09 |
2.휴가 (0) | 2022.11.09 |