[Python-CodingTest] 6-7. 동전교환 (DFS: 깊이우선탐색)

동전교환

문제 정리

입력

3
1 2 5
15

처리 과정

1. 레벨(=L)과 동전의 합(=sum)을 파라미터로 갖는 DFS() 선언
2. 동전 리스트(=coin)를 내림차순 정렬 한 뒤 큰 수부터 sum에 누적하며 재귀
3. sum이 m일 때의 레벨(=L)로 min 갱신

출력

3

내 답

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

def DFS(L,sum):
    global m
    if sum>m:
        return
    else:
        for x in coin:
            while m>=x:
                res.append(x)
                m-=x
                DFS(L+1,sum+x)


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

    coin.sort(reverse=True)
    res=[]

    DFS(0,0)
    print(len(res))

테스트 케이스 정답률: 4/5

풀이 - 1

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

def DFS(L,sum): # L은 레벨(Level)
    global min
    if sum>m:
        return
    if sum==m: # sum이 m일 때의 레벨로 min 갱신
        if L<min: 
            min=L
    else:
        for x in coin:
            DFS(L+1,sum+x)
  
if __name__=="__main__":
    n=int(input())
    coin=list(map(int,input().split()))
    m=int(input())

    coin.sort(reverse=True)
    min=2147000000 # 동전의 최소 개수
    
    DFS(0,0)
    print(min)

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

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

def DFS(L,sum): # L은 레벨(Level)
    global min
    if L>min: # 새로운 min을 갱신하는 것만 의미있음 (레벨이 min보다 크다면 더 가볼필요 없음)
        return
    if sum>m:
        return
    if sum==m:
        if L<min: 
            min=L
    else:
        for x in coin:
            DFS(L+1,sum+x)
  
if __name__=="__main__":
    n=int(input())
    coin=list(map(int,input().split()))
    m=int(input())

    coin.sort(reverse=True)
    min=2147000000

    DFS(0,0)
    print(min)

정리

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

---

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

맨 위로 이동하기