アルゴリズム学習2)3月3日

Intro

2839号送糖

解法

正しいコード

N = int(input())

d = [5001] * (N+3)
d[3] = 1
d[5] = 1

for i in range(6, N+1) :
    d[i] = min(d[i-3]+1, d[i-5]+1)

if d[N] >= 5001:
    print(-1)
else:
    print(d[N])

作成1463号1

解法

正しいコード

N = int(input())

d = [0] * (N+1)

for i in range(2, N+1):

    d[i] = d[i-1] + 1

    if i % 3 == 0:
        d[i] = min(d[i], d[i//3] + 1)
    if i % 2 == 0 :
        d[i] = min(d[i], d[i//2] + 1)
        

print(d[N])

2579番の階段を上る

解法

正しいコード

n = int(input())

score = []
for i in range(n):
    score.append(int(input()))

if n == 1:
    print(score[0])
else:
    dp = [0]*(n+1)
    dp[1] = score[0]
    dp[2] = score[0] + score[1]

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

    print(dp[n])

1912回連続

解法

正しいコード

n = int(input())
num = list(map(int, input().split()))

dp = [0] * n
dp[0] = num[0]

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

print(max(dp))

11726号2 xnタイル

解法

実際、この問題は以前は解答したことがあるが、次の問題と比較するために書いた.

正しいコード

n = int(input())
tiles = [0]*1001
tiles[1] = 1
tiles[2] = 2

for i in range(3, n+1):
    tiles[i] = tiles[i-1]+tiles[i-2]

print(tiles[n]%10007)

11727号2 xnタイル2

解法

正しいコード

n = int(input())

d = [0] * (n+1)

if n == 1:
    d[1] = 1
    print(d[1]%10007)
else:
    d[1] = 1
    d[2] = 3

    if n == 2:
        print(d[2]%10007)
    else:
        for i in range(3, n+1):
            d[i] = 2*d[i-2] + d[i-1]

        print(d[n]%10007)

1890号ジャンプ台

解法

正しいコード

N = int(input())
map = [list(map(int, input().split())) for i in range(N)]

dp = [[0] * N for i in range(N)]
dp[0][0] = 1

for i in range(N):
    for j in range(N):
        if i==N-1 and j==N-1:
            break

        right = j + map[i][j]
        bottom = i + map[i][j]

        if right < N:
            dp[i][right] += dp[i][j]
        if bottom < N:
            dp[bottom][j] += dp[i][j]

print(dp[N-1][N-1])