BAEKJOON : 2156, 1932

2447 ワード
コーディングテスト テキストリンク

No. 2156


1. Problem

2. My Solution
  • 二次元DPプール
  • i 2本目のワインは、3つのケースに分かれています
    -i 2杯目のワインは飲まない(OOX)
    -i号ワイン、i-1ワイン、i-2ワイン(OXO)
    -第i種ワインも飲めばi-1ワイン(XOO)
  • iの2種類目のワインを飲まない場合、dp[n-1][2]では求めることができず、dp[n-1]で最大値(例えば、10個のワインがある場合、10種類目のワインを飲まない場合、無条件に8、9種類のワインを飲む場合よりも)
    • をとることになる.
    import sys

n = int(sys.stdin.readline().rstrip())
juices = []

for _ in range(n):
    juices.append(int(sys.stdin.readline().rstrip()))

dp = [[0,0,0] for _ in range(n)]
dp[0][1] = dp[0][2] = juices[0]

for i in range(1,n):
    dp[i][0] = max(dp[i-1])
    dp[i][1] = dp[i-1][2] + juices[i]
    dp[i][2] = dp[i-1][0] + juices[i]

print(max(dp[n-1]))
    3. Others' Solutions
  • 1次元DPプール
  • i第3種ワインが3種類に分かれている場合
    2杯目のワインを飲まないと
    -i-1型ワインではなくi-2型ワイン
    -i-1ワインも飲めば
  • 3の場合の数字は次のように表示されます.
    - dp[i-1]
    - juices[i]+dp[i-2]
    -ジュース[i]+ジュース[i-1]+dp[i-3](i-3の最大値を加算)
    • # dp[i] -> i = n, n 일때 최대 포도주양 
                         
import sys

n = int(sys.stdin.readline().rstrip())
juices = [0]

for _ in range(n):
    juices.append(int(sys.stdin.readline().rstrip()))

dp = [0] * (n+1)
dp[1] = juices[1]

if n > 1:
    dp[2] = juices[1] + juices[2]

for i in range(3,n+1):
    temp = []
    temp.append(dp[i-1])
    temp.append(juices[i]+juices[i-1]+dp[i-3])
    temp.append(juices[i]+dp[i-2])

    dp[i] = max(temp)

print(dp[n])
    4. Learned
  • 最低価格または最高価格は
    • であるべきである.

    No. 1932


    1. Problem

    2. My Solution
  • このレベル(レイヤ)がj番目の要素で終わるときの最大値はそれぞれ
    • である.
    # dp[i][j] -> i = n, j = 0 ~ level-1 (해당 층에서 j 번째 요소로 끝나는 경로의 최댓값) 
                         
import sys

n = int(sys.stdin.readline().rstrip())
dp = [[0]* n for _ in range(n+1)]

level = [[0]]
for _ in range(n):
    level.append(list(map(int,sys.stdin.readline().rstrip().split())))

dp[1][0] = level[1][0]

for i in range(2,n+1):
    for j in range(0,i):
        if j == 0:
            dp[i][j] = dp[i-1][j] + level[i][j]
        elif j == i-1:
            dp[i][j] = dp[i-1][j-1] + level[i][j]
        else:
            dp[i][j] = max(dp[i-1][j-1] + level[i][j], dp[i-1][j] + level[i][j])

print(max(dp[n]))
    rman管理4 CATALOG DB
    プログラマを区切る数字配列(JavaScript)