Jinho Tech

기본적인 우선순위 큐 문제이다.

import heapq
import sys
input = sys.stdin.readline

N = int(input()) 
q = []
for _ in range(N):
    n = int(input())
    if n != 0:
        heapq.heappush(q, n)
    else:
        print(heapq.heappop(q) if q else 0)

기본적인 우선순위 큐 문제이다.

import heapq
import sys
input = sys.stdin.readline

N = int(input()) 
q = []
for _ in range(N):
    n = int(input())
    if n != 0:
        heapq.heappush(q, -n)
    else:
        print(-heapq.heappop(q) if q else 0)

기본적인 다이나믹 프로그래밍 문제이다. 1차원 DP처럼 똑같이 해주면 된다. 

N, M = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(N)]
dp = [[0]*M for _ in range(N)]
dp[0][0] = li[0][0]
for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            continue
        elif i > 0 and j == 0:
            dp[i][j] = dp[i-1][j]
        elif i == 0 and j > 0:
            dp[i][j] = dp[i][j-1]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        if li[i][j] == 1:
            dp[i][j] += 1
print(max(map(max, dp)))

기본적인 다이나믹 프로그래밍 문제이다. 

N = int(input())
li = list(map(int, input().split()))
dp = [N+1]*N
dp[0] = 0
for i in range(N):
    for j in range(1, li[i]+1):
        if i+j >= N:
            break
        dp[i+j] = min(dp[i+j], dp[i]+1)
print(dp[N-1] if dp[N-1] != N+1 else -1)

기본적인 다이나믹 프로그래밍 문제이다.

import sys
input = sys.stdin.readline

while 1:
    N = int(input())
    if N == 0:
        break
    li = [int(input()) for _ in range(N)]
    for i in range(1, N):
        li[i] = max(li[i], li[i]+li[i-1])
    print(max(li))

기본적인 다이나믹 프로그래밍 문제이다.

n = int(input())
li = list(map(int, input().split()))
dp = [1]*n
for i in range(1, n):
    for j in range(i):
        if li[i] > li[j]:
            dp[i] = max(dp[i], dp[j]+1)
print(max(dp))

기본적인 다이나믹 프로그래밍 문제이다. 

N = int(input())
li = list(map(int, input().split()))
dp1, dp2 = [1]*N, [1]*N
for i in range(1, N):
    if li[i] <= li[i-1]:
        dp1[i] = max(dp1[i], dp1[i-1]+1)
    if li[i] >= li[i-1]:
        dp2[i] = max(dp2[i], dp2[i-1]+1)
print(max(max(dp1), max(dp2)))

간단한 브루트포스 알고리즘 & 문자열 문제이다.

A, B = input().split()
la, lb = len(A), len(B)
res = la
for i in range(lb-la+1):
    t = 0
    for j in range(la):
        if A[j] != B[i+j]:
            t += 1
    res = min(res, t)
print(res)

기본적인 다이나믹 프로그래밍 문제이다. 자기 앞에 자기보다 작은 수가 없는 경우도 있는데,

이 부분만 주의하면 쉽게 풀 수 있다.

from copy import deepcopy

N = int(input())
li = list(map(int, input().split()))
dp = deepcopy(li)
for i in range(1, N):
    for j in range(i):
        if li[j] < li[i]:
            dp[i] = max(dp[i], li[i]+dp[j])
print(max(dp))

기본적인 다이나믹 프로그래밍 문제이다.

N = int(input())
li = list(map(int, input().split()))
dp = [1]*N
for i in range(1, N):
    for j in range(i):
        if li[i] < li[j]:
            dp[i] = max(dp[i], dp[j]+1)
print(max(dp))

단순 수학 문제이다.

A, B = map(int, input().split())
res = 0
for i in range(A+1, 63):
    if int(str(2**i)[0]) == B:
        res = i
        break
print(res)

기본적인 다이나믹 프로그래밍 문제이다. 뒤쪽 대각선 방향으로 첫 번째, 두 번째 위치의 값 중 큰 걸 선택하면 된다.

dp[0][j] += max(dp[1][j-1], dp[1][j-2]) 

dp[1][j] += max(dp[0][j-1], dp[0][j-2])

for _ in range(int(input())):
    n = int(input())
    dp = [[0]+list(map(int, input().split())) for _ in range(2)]    
    for j in range(2, n+1):
        dp[0][j] += max(dp[1][j-1], dp[1][j-2])
        dp[1][j] += max(dp[0][j-1], dp[0][j-2])
    print(max(dp[0][n], dp[1][n]))

기본적인 다이나믹 프로그래밍 문제이다.

N = int(input())
dp = [[0]*10 for _ in range(N+1)]
for i in range(10):
    dp[1][i] = 1
for i in range(2, N+1):
    for j in range(10):
        for k in range(j+1):
            dp[i][j] += dp[i-1][k]
print(sum(dp[N])%10007)

단순 구현 문제이다.

import sys
input = sys.stdin.readline

N, T = map(int, input().split())
d = [(1, 0), (0, -1), (-1, 0), (0, 1)]
i = X = Y = 0
li = [0]
for _ in range(N):
    time, s = input().split()
    time = int(time)
    t = time-li[-1]
    li.append(time)
    x, y = d[i][0], d[i][1]
    X += t*x; Y += t*y
    i += 1 if s == 'right' else -1
    i = i%4
t = T-li[-1]
x, y = d[i][0], d[i][1]
X += t*x; Y += t*y
print(X, Y)

기본적인 다이나믹 프로그래밍 문제이다.

def dfs(n):
    if n == M:
        print(*t)
        return ;
    for i in range(N):
        if check[i]:
            continue
        t.append(li[i])
        check[i] = 1
        dfs(n+1)
        t.pop()
        check[i] = 0

N, M = map(int, input().split())
li = sorted(map(int, input().split()))
check = [0]*N
t = []
dfs(0)