[ baekjoon ] 14501. 退社する

14501.退社

質問する

コンサルタントの白俊さんが会社を辞めます.
今日からN+1日で辞めるために、残りのN日にできるだけ多くの相談をします.
白俊は秘書にできるだけ多くの相談を依頼し、秘書は1日に1回異なる人に相談を手配した.
各コンサルティングは,コンサルティングを完了するのに要する時間内にTIとコンサルティングを行う際に得られる金額Piからなる.
N=7の場合は、以下のコンサルティングスケジュールを参照してください.

1日のカウンセリングは全部で3日かかりますが、カウンセリング時にもらえる金額は10です.5日間のお問い合わせは2日間かかりますが、受け付けられる金額は15です.
相談にかかる時間は1日以上かかる場合がありますので、すべての相談はできません.例えば、1日に問い合わせを行った場合、2日、3日に問い合わせをすることはできません.2日に問い合わせをすれば、3、4、5、6日には問い合わせができない.
なお、N+1日は会社にいないため、6,7日は相談できません.
退職前にカウンセリングを行う最大の利益は1日、4日、5日にカウンセリングを行うことであり、その際の利益は10+20+15=45である.
商談がうまくいけば、白俊に最大の収益をもたらす計画を立ててください.

入力

第1行はN(1≦N≦15)を与える.
2行目からN行目まで、TIとPiはスペースで区切られ、1日からN日まで順次与えられる.(1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

しゅつりょく

1行目は白俊が得られる最大の利益を出力する.

✔ソースコード1

import sys
input = sys.stdin.readline

n = int(input())

dp = [[0 for j in range(n)] for i in range(n + 1)] # 다이나믹 프로그래밍
result = [0] * (n + 1)

for i in range(n):
  a, b = map(int, input().split())
  if i + a <= n: # 일 수를 포함해 n일을 넘지 않는 조건에만 
    result[i] = b
    for j in range(i, i + a):
      dp[i][j] = b

  idx = n # 이 코드 없으면 index error
  check = False
  for j in range(i):
    if dp[j][i] == 0: # 합칠 수 있는 조건
      check = True
      if result[j] > result[idx]: # 최댓값을 해당 dp 배열에 합친다.
        idx = j

  if check: # 합칠 수 있을 때 
    result[i] += result[idx]
    for k in range(i):
      dp[i][k] = dp[idx][k]  

print(max(result))

✔ソースコード2

import sys
input = sys.stdin.readline

n = int(input())
table = []
for i in range(n):
  a, b = map(int, input().split())
  table.append((a, b))

dp = [0] * (n + 1) # 다이나믹 프로그래밍

for i in range(n - 1, -1, -1):
  if table[i][0] + i <= n: # 일수가 넘어가지 않을 때 
    dp[i] = max(table[i][1] + dp[i + table[i][0]], dp[i + 1])
  else:
    dp[i] = dp[i + 1]

print(dp[0])

両方のメソッドのメモリ量は同じです.
最初の方法で解きました
他の方法を探すとき、第2の方法はもっと直感的に理解できるので、持ってきました.
2つの方法の共通点は、宣言された1次元アレイをn+1サイズとして宣言する必要があることです.
(改めて、第1の方法のdp配列はresultのようですが・・・
DPアルゴリズムの問題だと知ってアクセスしたので、DPでネーミングしたようです)
1つ目の方法は,2次元配列(NxN)にすべて格納した後,重ならない配列をマージして解くことである.
2つ目の方法は,最終日から条件をチェックしながらDP配列を更新することである.
nを超えない条件、持続時間を含む
第1の方法のif i + a <= n:=第2の方法のif table[i][0] + i <= n: