[Python-CodingTest] 7-2. 휴가 (삼성 SW역량평가 기출문제 : DFS활용)

휴가

문제 정리

입력

7
4 20
2 10
3 15
3 20
2 30
2 20
1 10

처리 과정

1. 상담 일수와 금액을 리스트에 담기
2. v(상담 날짜)가 n일 때까지는 else에서 처리하고 n+1일 때 max를 갱신한다.
3. 상담을 진행하기 전에, 그 상담을 진행하고 나서 n+1을 넘지 않는지 확인한다. (이때 n이 아니라 n+1임을 주의!)
4. 넘지 않는다면 상담을 진행하고, DFS() 재귀호출 할 때 v+1이 아니라 그 상담에 걸리는 일수를 더한다.
5. 상담을 진행하지 않았다면, v+1 한다.

출력

60

내 답

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

def DFS(v,day_sum,pay_sum): # 상담 날짜(-일) # day_sum은 몇 건의 상담을 하는데 걸린 누적 일수
    global max
    if day_sum>n:
        return
    if v==n+1: # 7일까지는 else에서 처리해야함
        if pay_sum>max:
            max=pay_sum
    else:
        # 🌟 중요한건 1일에 상담을 진행했다면 그 상담은 4일이 걸리니까 다음 상담은 5일부터 가능!
        DFS(v+counsel[v][0],day_sum+counsel[v][0],pay_sum+counsel[v][1]) # 상담O # 다음 날짜(v+counsel[v][0])로 넘어가고, sum과 day의 누적값은 현재 문제(v) 기준!
        DFS(v+counsel[v][0],day_sum,pay_sum) # 상담X

if __name__=="__main__":
    n=int(input())
    counsel=[[0]*2 for _ in range(n+1)] # 1일~7일 (인덱스번호 맞추기)

    for i in range(1,n+1):
        counsel[i][0],counsel[i][1]=map(int,input().split())
    # counsel[][0]: 상담 완료까지 걸리는 날 수
    # counsel[][1]: 상담 완료시 받는 금액

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

🚨 상담을 하기 전에 if v+counsel[v][0]<=n+1:으로 조건 확인해야 함!
위에처럼 if문으로 조건 확인하면, DFS()의 인자로 day_sum은 넣을 필요 없음

풀이

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

def DFS(v,pay_sum): # v: 상담 날짜(-일) # pay_sum: 누적 금액
    global res
    if v==n+1: # 7일까지는 else에서 처리해야함
        if pay_sum>res:
            res=pay_sum
    else:
        if v+cd[v]<=n+1: # 🌟 7일날 상담은 하루만에 끝나니까 진행할 수 있음 -> n이 아니라 n+1(=8)보다 작거나 같아야 함!
            DFS(v+cd[v],pay_sum+cp[v]) # 상담O # 🌟 1일에 상담을 진행했다면 그 상담은 4일이 걸리니까 다음 상담은 5일부터 가능!
        DFS(v+1,pay_sum) # 상담X -> 다음 날짜로 이동 (v+1)

if __name__=="__main__":
    n=int(input())

    cd=list() # counsel day: 상담 완료까지 걸리는 날 수
    cp=list() # counsel pay: 상담 완료시 받는 금액

    for i in range(n):
        a,b=map(int,input().split())
        cd.append(a)
        cp.append(b)

    res=0 # max값
    cd.insert(0,0) # 리스트의 0번 인덱스에 0 집어넣음 (인덱스 번호랑 날짜 맞추기 위해 하나씩 뒤로 밀기)
    cp.insert(0,0)

    DFS(1,0)
    print(res)

정리

• 중요한 논리

  1. 상담을 진행하기 전, 조건(if v+cd[v]<=n+1:) 확인해야 함
     (Ex. 7일날 상담은 하루만에 끝나니까 진행할 수 있음 -> n이 아니라 n+1(=8)보다 작거나 같아야 함!)
     
  2. 상담을 진행했다면 이후 DFS 호출 시 그 상담을 진행하는데 필요한 일 수를 더해서 호출해야 함
     (Ex. 1일에 상담을 진행했다면 그 상담은 4일이 걸리니까 다음 상담은 5일부터 가능!)

---

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

맨 위로 이동하기