[Python-CodingTest] 7-1. 최대 점수 구하기 (DFS)

최대 점수 구하기

문제 정리

입력

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

처리 과정

1. 문제의 점수와 푸는데 걸리는 시간을 리스트에 담기
2. v(문제 번호)가 n일 때까지는 else에서 처리하고 n+1일 때 max를 갱신한다.
3. 문제를 푸는 상황에서 DFS() 재귀호출 할 때, 다음 문제 번호(v+1)와 점수누적, 시간누적을 넘긴다.
4. 문제를 풀지 않는 상황에서 DFS() 재귀호출 할 때, 다음 문제 번호(v+1)만 넘기고 점수와 시간은 누적하지 않는다.
5. 시간을 누적한 값이 제한시간을 넘어가면 안된다.

출력

41

내 답

import sys
sys.stdin = open("./input/in1.txt", "rt")

def DFS(v,score_sum,time_sum): # (문제번호,점수누적,시간누적)
    global max
    if time_sum>m: # 제한 시간을 넘어가면 안됨
        return
    if v==n+1: # v가 5까지는 else에서 처리해야함
        if score_sum>max: 
            max=score_sum # 최대 점수 갱신
    else:
        DFS(v+1,score_sum+quest[v][0],time_sum+quest[v][1]) # 점수,시간 누적
        DFS(v+1,score_sum,time_sum)

if __name__=="__main__":
    n,m=map(int,input().split())

    quest=[[0]*2 for _ in range(n+1)] # 문제들(questions) # n+1 -> 문제번호와 인덱스 번호 일치 
    for i in range(1,n+1):
        quest[i][0],quest[i][1]=map(int,input().split())

    max=0
    DFS(1,0,0) # 1번 문제가 루트 노드
    print(max)

문제의 점수와 시간을 입력받기 위해 2차원 리스트(quest[][]) 사용
문제 번호와 문제 리스트의 인덱스를 일치 (1번 문제의 점수: quest[1][0] 시간: quest[1][1])

풀이

import sys
sys.stdin = open("./input/in1.txt", "rt")

def DFS(v,score_sum,time_sum): # (문제번호,점수누적,시간누적)
    global res
    if time_sum>m:
        return
    if v==n:
        if score_sum>res:
            res=score_sum
    else:
        DFS(v+1,score_sum+ps[v],time_sum+pt[v]) # 풀었을 때
        DFS(v+1,score_sum,time_sum) # 안풀었을 때

if __name__=="__main__":
    n,m=map(int,input().split())

    ps=list() # problem score: 문제 점수
    pt=list() # problem time: 푸는데 걸린 시간

    for _ in range(n):
        a,b=map(int,input().split())
        ps.append(a)
        pt.append(b)

    res=0 # max 값
    DFS(0,0,0) # 0번 노드가 첫번째 문제
    print(res)

문제의 점수와 시간을 입력받기 위해 리스트 2개(qs[],qt[]) 사용
문제 번호와 문제 리스트의 인덱스가 일치X (1번 문제의 점수: qs[0] 시간: qt[0])

정리

• ‘6-3. 부분집합 구하기’에서는 사용할 원소(=1)와 사용하지 않을 원소(=0)를 구분하는 체크리스트(ch[])를 활용했는데, 여기서는 체크리스트는 따로 필요 없음!
• 점수와 시간을 받기 위해서 2차원 리스트를 사용해도 되고, 1차원 리스트 두개를 사용해도 된다.

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기