문제 요약
# N : day
# T : 상담을 완료하는데 걸리는 시간
# P : 상담을 했을 때 받을 수 있는 금액
# N일 동안 상담을 해서 최대한 많은 이익을 얻는 방법
첫 번째 구현 → 실패
def dfs(시작점):
# 현재 일수가 N보다 큰 상황 -> 뒤 돌아간다.(백트래킹)
if 현재일수 > N:
return
## dfs는 T를 기준으로 방문한 T가 N을 넘지 않으면 계속 방문
## T를 방문하면 i + T[i] 가 되어야한다.
for i in range(시작점,n+1):
if visited[i] == 0:
continue
visited[i] = 1 # 방문처리
s.append(P[i]) # 현재 cost 추가
dfs(i+T[i])
s.pop()
vistied[i] = 0
return 방문 노드의 cost 합
result = 0
for i in range(N):
visited = [0] * n
c = [] # 모든 cost 값 저장
dfs(i)
result = max(result , sum(c))
print(result)
- 시작점을 다르게하며 모두 확인을 하는 과정이 있어서 visited를 통해서 방문 현황을 확인할 필요가 없었다.
- dfs 바깥부분에서 result = max(result, sum(c))로 인해서 정확한 결과가 나오지 않았다.
- 이 부분은 dfs 시작 부분에서 처리가 되어야 했다.
두 번째 구현 → 성공
def dfs(시작점):
# 현재 일수가 N보다 큰 상황 -> 뒤 돌아간다.(백트래킹)
if 현재일수 > N:
return
result = max(result , 현재까지의 전체 cost 합)
## dfs는 T를 기준으로 방문한 T가 N을 넘지 않으면 계속 방문
## T를 방문하면 i + T[i] 가 되어야한다.
for i in range(시작점,n+1):
s.append(P[i]) # 현재 cost 추가
dfs(i+T[i])
s.pop()
result = 0
for i in range(N):
c = [] # 모든 cost 값 저장
dfs(i)
print(result)
구현 코드
def dfs(start):
global result
if start > n:
return
result = max(result, sum(c))
for i in range(start , n):
c.append(p[i])
dfs(i + t[i])
c.pop()
t = []
p = []
n = int(input())
for _ in range(n):
a,b = map(int,input().split())
t.append(a)
p.append(b)
result = 0
for i in range(n):
c = []
dfs(i)
print(result)
'알고리즘 > 백준' 카테고리의 다른 글
백준-20546-기적의 매매법 (0) | 2024.07.12 |
---|---|
백준-2839-설탕 배달 (1) | 2024.07.03 |
백준-11497-통나무 건너뛰기 (0) | 2024.07.03 |
백준-14502-연구소 (1) | 2024.07.01 |
백준-14248-점프 점프 (0) | 2024.06.25 |