백준 온라인 저지: 문제 풀러 가기

1. 문제 요약

N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	10	20	10	20	15	40	200

예제입력 1)

7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

 

알고리즘 분류: 백트래킹

2. 접근 방식

1. 완전 탐색으로 접근.
2. 현재 날짜를 depth로 갖는 상태 트리를 그리고, depth가 제한 기간을 넘길때 가지치기
3. PROFIT!

풀이 >

# 현재 날짜 d(day) 와 현재 소득 money를 인자로 가지는 함수 solve 선언
def solve(d:int, money:int):
    global maxnow # 전역 변수 maxnow에 현재까지 도달한 최대 이익 저장
    if d >= N: # 종료조건. 현재 날짜가 퇴사일에 도달
        if money > maxnow: # 최대값이 갱신될경우 새로운 최대값을 저장하고 리턴
            maxnow = money
        return
    if d + arr[d][0] <= N: # 가지치기, 현재 날짜의 상담이 실현 가능한 경우만
        solve(d+arr[d][0], money + arr[d][1]) # 상담 실행
    solve(d+1, money) # 상담하지 않고 내일로 진행
    
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
# 입력
maxnow = -1
# 최대값 초기화
solve(0, 0)
print(maxnow)

3. 감상

• 가장 기초적인 형태의 백트래킹 문제.

  • 선택의 결과를 매개 변수로 받아서 다음 상태로 진행하는 형태

• DP로도 풀수있다. (시간차이 x)

  • 크기 N인 배열을 선언하고 뒤에서부터 상담 가능할때 이익금을 쌓아나가는 형태

  N = int(input())
  memo = [0] * N
  arr = [list(map(int, input().split())) for _ in range(N)]
  if arr[N-1][0] == 1:
      memo[N-1] = arr[N-1][1]
  for i in range(N-2, -1, -1):
      d = i + arr[i][0]
      if d == N:
          memo[i] = max(arr[i][1], memo[i+1])
      elif d < N:
          memo[i] = max([arr[i][1] + memo[d], memo[i+1]])
      elif d > N:
          memo[i] = memo[i+1]
  print(memo[0])