[Python-CodingTest] 6-5. 바둑이 승차 (DFS: 깊이우선탐색)

바둑이 승차

문제 정리

입력

259 5
81
58
42
33
61

처리 과정

1. i가 n과 같지 않을 때, DFS에 다음 인덱스(=i+1)와 누적합(=sum)을 전달
2. 이때 누적합은 원소로 사용될 때는 해당 lst 값을 누적하고, 사용되지 않을 때는 그대로 전달
3. n-1까지 계산한 뒤, i가 n이 되면, 누적합으로 최댓값을 갱신
4. 누적합(=sum)이 c보다 클 때는 return

출력

242

내 답

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

def DFS(i,sum):
    global max # 🌟 2. 전역변수 max 사용
    if i==n:
        if sum>max and sum<c:
                max=sum # 1. max는 지역변수로 선언
    else:
        DFS(i+1,sum+lst[i]) # 포함
        DFS(i+1,sum) # 포함X
    


if __name__=="__main__":
    c,n=map(int,input().split())
    lst=[]
    for i in range(n):
        lst.append(int(input()))
    max=0

    DFS(0,0)
    print(max)

풀이 - 1

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

def DFS(i,sum): # i는 인덱스 번호, sum은 원소의 누적 합
    global max # 전역변수 max 사용
    if sum>c: # c를 넘지 않는 누적합을 구하기 위한 조건
        return
    if i==n: # 부분집합 하나 완성
        if sum>max:
            max=sum 
    else:
        DFS(i+1,sum+lst[i])
        DFS(i+1,sum)
    


if __name__=="__main__":
    c,n=map(int,input().split())
    lst=[0]*n
    for i in range(n):
        lst[i]=int(input())

    max=0
    DFS(0,0)
    print(max)

풀이 - 2: Cut-Edge (실행시간 줄이기)

import sys
sys.stdin = open("./input/in5-1.txt", "rt")

def DFS(i,sum,tsum): # tsum은 total_sum으로 판단한 요소들의 무게합
    global max
    if sum+(total-tsum)<max: # total-tsum은 앞으로 적용할 요소(바둑이)들의 무게합
        return
    if sum>c: 
        return
    if i==n: 
        if sum>max:
            max=sum 
    else:
        # 판단을 한 요소는 (부분집합에 포함했건 안했건) 무조건 tsum에 누적 
        DFS(i+1,sum+lst[i],tsum+lst[i])
        DFS(i+1,sum,tsum+lst[i])
    
if __name__=="__main__":
    c,n=map(int,input().split())
    lst=[0]*n
    for i in range(n):
        lst[i]=int(input())
    total=sum(lst)
    max=0

    DFS(0,0,0)
    print(max)

정리

• global: 전역변수를 사용하기 위한 키워드

---

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

맨 위로 이동하기