[백준] 14501번

https://www.acmicpc.net/problem/14501

 

 

처음 접근 방식

- 수기로 작성해보면서 해보니 "가능한 모든 경우를 다 실행해보고 그 중에서 max를 찾으면 될 수도 있겠다" 싶어서 완전탐색(백트래킹)도 생각났고, - "그림처럼 큰 문제를 여러 방식으로 쪼개는 느낌"이라 dp 도 적용가능하겠다. 라는 생각이 들었다.

➡️ 최대 15일까지로 정해져있기 때문에 연산량이 생각보다 그렇게 크지 않을 것이므로 완전탐색과 dp 모두 가능!

 

상담이 가능한 조건 : 항상 7일 내에 상담이 끝나야 하고, 만약 i일차에 상담을 했다면 T[i]일 동안은 상담이 불가

즉, 식으로 표현하면 n<=T[n] 

 

그리고 가장 중요한 수익 ans는 갱신해주면 됨

 

여기까지는 생각했는데 코드로 구현하는 것이 헷갈렸었음

 

방법 1) 백트래킹

복잡도 2^15

def dfs(n,sum) : 
    global ans
    # 종료조건 : 가능한 n을 종료에 관련된 것으로 정의
    if n>=N : 
        ans = max(ans,sum)
        return
    
    # 하부 호출 : 화살표 개수만큼 호출
    if n+T[n] <= N : # 상담하는 경우 (퇴사일 전 상담이 완료 가능)
        dfs(n+T[n], sum+P[n])
    dfs(n+1, sum)# 상담하지 않는 경우 (항상 가능)

N = int(input())
T = [0]*N
P = [0]*N
for i in range(N) : 
    T[i], P[i] = map(int, input().split())
    
ans = 0
dfs(0,0)
print(ans)

 

참고로 그냥 return이라고 쓰면 그렇게 함수가 끝남. 그래서 print(ans) 라고 써준것.

 

방법 2)   

💡 역방향이 가끔 더 좋은 풀이를 만든다.

앞에서부터 체크하면 이중으로 체크해야할 일이 생긴다.

N = int(input())
T = [0] * N
P = [0] * N

for i in range(N): 
    T[i], P[i] = map(int, input().split())
    
dp = [0] * (N + 1)  # dp 배열 초기화

for n in range(N - 1, -1, -1):  # 뒤에서 앞으로 계산
    if n + T[n] <= N: 
        dp[n] = max(dp[n + 1], dp[n + T[n]] + P[n])  # 상담 가능
    else: 
        dp[n] = dp[n + 1]  # 상담 불가능

print(dp[0])  # 최대 수익 출력