인프런 - 코딩테스트 강의 Section 7. 깊이, 넓이 우선탐색 활용

Section 7. 깊이, 넓이 우선탐색 활용

 

7.1. 최대점수 구하기(DFS)

• L을 인덱스값으로

import sys
sys.stdin=open("input.txt", "r")

def DFS(L, total_p, total_t):
    global max
    if total_t >  m: # 제한시간 넘어가면
        return
    if L==n:
        if total_p >= max:
            max = total_p
    else:
        DFS(L+1, total_p + a[L][0], total_t + a[L][1])
        DFS(L+1, total_p, total_t )


n, m = map(int, input().split())
max = -2147000000
a = []
for _ in range(n):
    p, v = map(int, input().split())
    a.append((p, v))

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

 

7.2. 휴가(삼성 SW역량평가 기출문제 : DFS활용)

• 풀이랑 답 다른데 왜 맞았지

import sys
sys.stdin=open("input.txt", "r")

def DFS(L, sum):
    global max
    if L==n:
        if sum > max:
            max = sum
    else:
        if L+a[L][0] <= n:
            DFS(L+a[L][0], sum+a[L][1]) # 날짜에 일함
        DFS(L+1, sum) # 날짜에 일 안하고 건너 뜀


n = int(input())
a = []
for _ in range(n):
    t, p = map(int, input().split())
    a.append((t,p))
max = -2147000000
DFS(0, 0)
print(max)

 

7.3 양팔저울(DFS)

뭔소리지ㅜㅜ

 

7.4 동전 바꿔주기(DFS)

• 뭘 잘못했지 꼭 다시 풀어보자

#### 오답!!
def DFS(L, sum):
    global cnt
    if L == len(a):
        return
    if sum == T:
        print(L, sum)
        cnt += 1
        return
    else:
        DFS(L+1, sum + a[L])
        DFS(L+1, sum)

import sys
sys.stdin=open("input.txt", "r")

def DFS(L, sum):
    global cnt
    if sum>T:
        return
    if L == k:
        if sum == T:
            cnt += 1
        # 여기서 return을 하지 않는 이유는, 
        # 다음 LV에서 sum>T인 경우 return을 하기 떄문이다.
    else:
        for i in range(a[L][1]+1):
            DFS(L + 1, sum + a[L][0] * i)

T = int(input())
k = int(input())
a = []
for _ in range(k):
    p, n = map(int, input().split())
    a.append((p, n))
cnt = 0
DFS(0, 0)
print(cnt)

 

 

7.5. 동전 분배하기(DFS)

• set() 자료구조에 요소 추가는 tmp.add(x)
• 각자 다른 금액을 받았는지 확인하기 위해 set을 사용한다.
• Back한 경우!! 그 전 상황으로 돌아가야 하는 것도 고려!!

import sys
sys.stdin=open("input.txt", "r")

def DFS(L):
    global minimum
    if L == n:
        if max(money) - min(money) < minimum:
            # 세 사람이 받은 금액이 다를 때만 변경해야 한다!!!
            # tmp = set()
            # for x in money:
            #    tmp.add(x)
            tmp = set(money)
            if len(tmp) == 3:
                minimum = max(money) - min(money)
    else:
        for i in range(3):
            money[i] += a[L]
            DFS(L+1)  # 다음 동전
            money[i] -= a[L] # Back한 경우!! 그 전 상황으로 돌아가야 함

n = int(input())
a = [int(input()) for _ in range(n)]
minimum = 2147000000
money = [0]*3
DFS(0)
print(minimum)