[WEEK05] DAY32 & TMI

DAY32

2579段阶(DP)

コード#コード#

import sys

n = int(sys.stdin.readline())
stairs = [int(sys.stdin.readline()) for _ in range(n)]
dp = [[0 for _ in range(2)] for _ in range(n)]
# dp[n] = n번째 계단까지 밟았을 때 최대 점수

if n == 1:
    print(stairs[0])
else:
    dp[0][0] = stairs[0]
    dp[1][0], dp[1][1] = stairs[1], stairs[1] + stairs[0]

    for i in range(2, n): # n번째 = i
        dp[i][0] = max(dp[i - 2][0], dp[i - 2][1]) + stairs[i] # 규칙2
        dp[i][1] = dp[i - 1][0] + stairs[i] # 규칙1

    print(max(dp[n - 1][0], dp[n - 1][1])) 

1202箸箸箸泥箸(グリディ、DFS)

コード#コード#

import sys
from heapq import heappush, heappop
input = sys.stdin.readline
n, k = map(int, input().split())
jewerly = tmp = []
for i in range(n):
    m , v = map(int, input().split())
    jewerly.append([m, v])
bag = [int(input()) for _ in range(k)]
jewerly.sort()
bag.sort()
result = i = 0
for b in bag:
    ## 현재 가방의 무게보다 무게가 작은 보석들을 찾음
    while i < n and jewerly[i][0] <= b:
        heappush(tmp, -jewerly[i][1])
        i += 1
    ## 가치가 제일 큰 보석을 tmp에서 빼고 result에 넣는다
    if tmp:
        result -= heappop(tmp)
print(result)

1520下坂(DP)

コード#コード#

import sys
input = sys.stdin.readline

# 상하좌우 방향
# 다음값이 현재 값보다 < 작을 때만 이동
# DP[N] = (n-1, n-1)까지 항상 내리막길로만 이동하는 경로의 개수

def dfs(x, y):
    if [x, y] == [N-1, M-1]:
        return dp[x][y]
    if dp[x][y] != -1: # 탐색한 길일 때
        return dp[x][y]
    dp[x][y] = 0 # 탐색한 길은 0(초깃값) 경로값은 가산할 예정
    for i in range(4):
        nx = x + dx[i] # 행
        ny = y + dy[i] # 열
        if 0<=nx<N and 0<=ny<M and arr[x][y] > arr[nx][ny]: # 범위 안에 있고, 이동할 좌표의 값이 현재위치 값보다 작으면
            dp[x][y] += dfs(nx, ny) # 경로 가산
    return dp[x][y]

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
dp = [[-1] * M for _ in range(N)] # -1 아니어도 됨
dp[-1][-1] = 1 # 최종 도착지
dx = [1, -1, 0, 0] # 하 상
dy = [0, 0, 1, -1] # 우 좌
print(dfs(0,0))