BAEKJOON : 1149, 1309, 11057

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

No. 1149


1. Problem

2. My Solution
  • iは数軒目を表し、jは家の色でdp[i][j](R=0,G=1,B=2)
    • を生成する.
  • i 1軒目の家RGBの最低コスト値は
    • に格納されています
  • i第1セットがR(0)に塗装されている場合、i-1セットがG(1)またはB(2)に塗装されている場合、
    • に塗装することができる.
    # dp[i][j] -> i = n, j = color (R = 0, G = 1, B = 2)

import sys

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

for _ in range(n):
    color_cost.append(list(map(int,sys.stdin.readline().rstrip().split())))

for i in range(3):
    dp[1][i] = color_cost[1][i]

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

print(min(dp[n]))

    No. 1309


    1. Problem

    2. Others' Solutions
  • n増加すると、左側にライオンがいない、右側にライオンがいない
    # dp[i][j] -> i = n, j = 사자의 위치 (0 = 없음, 1 = 왼쪽, 2 = 오른쪽)

import sys

n = int(sys.stdin.readline().rstrip())
dp = [[0,0,0] for _ in range(100001)]

for i in range(3):
    dp[1][i] = 1

for i in range(2,100001):
    dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) % 9901
    dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % 9901
    dp[i][2] = (dp[i-1][0] + dp[i-1][1]) % 9901

print(sum(dp[n]) % 9901)
    3. Learned
  • dpでnが増加した場合を考えると:

    • No. 11057


    1. Problem

    2. My Solution
  • 上り坂数は0で終わり、1で終わり...
    • (9で終わる)に分割
    dp[i][j]は、上り坂数の長さとjがどのように終わるかに関する情報を含む.
  • jで終わる上り坂数は、i-1の長さの上り坂数において、jがj以下である場合、jを加えると
    • になる.
    import sys

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

for i in range(10):
    dp[1][i] = 1

for i in range(1,n+1):
    for j in range(10):
        for k in range(j+1):
            dp[i][j] += dp[i-1][k] % 10007

print(sum(dp[n]) % 10007)
    白峻1520号:下り坂
    boj-7568(大きな塊)