.PNG)
56. 휴가(삼성 SW역량평가 기출문제 : DFS활용)
카운셀러로 일하고 있는 현수는 오늘부터 N+1일째 되는 날 휴가를 가기 위해서, 남은 N일 동안 최대한 많은 상담을 해서 휴가비를 넉넉히 만들어 휴가를 떠나려 한다.
현수가 다니는 회사에 하루에 하나씩 서로 다른 사람의 상담이 예약되어 있다.
각각의 상담은 상담을 완료하는데 걸리는 날수 T와 상담을 했을 때 받을 수 있는 금액 P로 이루어져 있다.만약 N = 7이고, 아래와 같이 예약이 잡혔있다면
1일에 잡혀있는 상담은 총 4일이 걸리며, 상담했을 때 받을 수 있는 금액은 20이다. 만약 1일에 예약된 상담을 하면 4일까지는 상담을 할 수가 없다.
하나의 상담이 하루를 넘어가는 경우가 많기 때문에 현수는 예약된 모든 상담을 혼자 할 수없어 최대 이익이 나는 상담 스케쥴을 짜기로 했다.
휴가를 떠나기 전에 할 수 있는 상담의 최대 이익은 1일, 5일, 7일에 있는 상담을 하는 것이며, 이때의 이익은 20+30+10=60이다.현수가 휴가를 가기 위해 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.
▣ 입력설명
첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.
둘째 줄부터 1일부터 N일까지 순서대로 주어진다. (1 ≤ T ≤ 7, 1 ≤ P ≤ 100)
▣ 출력설명
첫째 줄에 현수가 얻을 수 있는 최대 이익을 출력한다.
▣ 입력예제 1
7
4 20
2 10
3 15
3 20
2 30
2 20
1 10
▣ 출력예제 1
60
<내 풀이>
총체적 난국이다 그냥.. 1시간 40동안 낑낑댔는데 알듯말듯한 정도일 뿐이다.
===> 이러다가 해내고 말았다 이전 문제와는 뭔가 다른 부분이 있었는데 내가 그거를 간과하고 있었다. 그래서 내가 스스로 탐색트리를 만들어서 진행했더니 그것이 맞았다
def DFS(x,s,p) :
global largest
if s>n: #그리고 이 조건도 만들어줘서 순환이 끊기도록 가지치기 해줘야함
return
if s==n :
if largest<p:
largest=p
return
else :
DFS(x+1, s+1, p)
DFS(x+1, s+tp[s][0], p+tp[s][1]) #다만 처음에 이거를 구현하는 부분에서 어려움을 겪었음
if __name__=='__main__' :
tp=[]
n=int(input())
for i in range(n) :
a=list(map(int, input().split()))
tp.append(a)
largest = -100
DFS(0,0,0)
print(largest)
<풀이>
-처음 상담을 하냐 안하느냐로 갈리는 문제, 하게 되면 해당 t만큼의 날짜 다음에
아니라면 그냥 바로 다음 날짜로
#종료 지점은 n+1 이다
def DFS(x,sum) :
global res
if x==n+1 :
if sum>res:
res=sum
else :
if x+t[x] <=n+1:
DFS(x+t[x], sum+p[x]) #지금 상담하는 날 + 상담에 걸리는 날짜 = 다음에 상담가능한 날짜
DFS(x+1, sum)
if __name__=='__main__' :
n=int(input())
t=list()
p=list()
for i in range(n) :
a, b =map(int, input().split())
t.append(a)
p.append(b)
res=-100
t.insert(0,0) #밀어주는 것이다, 왜냐면 이거 인덱스 0부터 시작해서 이렇게 0,0 자리에 넣어주면 하나씩 밀려서 인덱스 1부터 자리가 차지 된다
p.insert(0,0)
DFS(1,0)
print(res)
<반성점>
- 처음에 문제를 잘 못 이해했다, 앞으론 문제를 신중하게 읽고 코드를 구현하도록
- return잘 지정해줘야 반복 에러 나지 않아요
<배운 점>
- dfs에서 잘못된 거 없는데 recursion errot, index out of range나면 계속 반복돼서 생기는 것이므로 가지치기 해서 끊어줘야 함
< 2차 내 풀이>
def dfs(x,s) :
global maxx
if x>n: #이 부분 안 해주면 index out of range난다 , 계속 돌려져서
return
if x==n:
if s>maxx:
maxx=s
else :
dfs(x+tmp[x][0],s+tmp[x][1] )
dfs(x+1, s)
if __name__=='__main__' :
maxx=-1
tmp=[]
n=int(input())
for i in range(n) :
a,b=map(int,input().split())
tmp.append((a,b))
print(tmp)
dfs(0,0)
print(maxx)