[인프런] 최대점수 구하기

---

문제설명

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

입력조건

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

출력조건

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

사고과정

• 각 문제를 푸느냐 마느냐로 두 개의 갈래길로 이루어진 상태트리를 만들어 DFS로 탐색하면서 최대 점수를 갱신하면 된다.
• 구현은 잘 했으나 강의 풀이와 비교해보니 불필요한 if 문이 너무 많았다.. 풀다가 중간에 헷갈려서 백트래킹하는 것도 따로 불필요하게 더 처리해주는 코드가 추가되었다.. 좀 간결하게 짜려고 노력해야겠다..

풀이

- 강좌 풀이(권장)

n, m = map(int, input().split())
pv = list()  # 점수
pt = list()  # 시간
for i in range(n):
    a, b = map(int, input().split())
    pv.append(a)
    pt.append(b)
res = -2147000000

def DFS(L, sum, time):
    global res
    if time > m:
        return
    if L == n:
        if sum > res:
            res = sum
    else:
        DFS(L+1, sum+pv[L], time+pt[L])
        DFS(L+1, sum, time)



DFS(0, 0, 0)  # 문제의 인덱스, 총점, 시간

 

- 나의 풀이(권장X)는 아카이브용으로 남기려 한다.

n, m = map(int, input().split())
arr = []
total_score = total_time = 0
for _ in range(n):
    score, time = map(int, input().split())
    arr.append((score, time))
    total_score += score
    total_time += time
answer = 0
# 너무 코드가 장황함...
def dfs(L, score, time):
    global answer
    if time > m:
        if score - arr[L-1][0] > answer:
            answer = score - arr[L-1][0]
        return
    if time == m:
        if score > answer:
            answer = score
        return
    if L == n:
        if time > m:
            if score - arr[L-1][0] > answer:
                answer = score - arr[L-1][0]
            return
        if time == m:
            if score > answer:
                answer = score
            return
    else:
        dfs(L+1, score+arr[L][0], time+arr[L][1])
        dfs(L+1, score, time)
# 예외 처리!!
if total_time <= m:
    print(total_score)
else:
    dfs(L=0, score=0, time=0)  # arr인덱스, 누적점수, 누적시간
    print(answer)