728x90
반응형

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

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))

 

728x90
반응형
728x90
반응형

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

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))
728x90
반응형
728x90
반응형

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

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)))
728x90
반응형
728x90
반응형

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

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)
728x90
반응형
728x90
반응형

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

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

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))
728x90
반응형
728x90
반응형

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

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))
728x90
반응형
728x90
반응형

단순 수학 문제이다.

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)
728x90
반응형
728x90
반응형

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

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]))
728x90
반응형
728x90
반응형

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

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)
728x90
반응형
728x90
반응형

단순 구현 문제이다.

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)
728x90
반응형
728x90
반응형

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

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)
728x90
반응형
728x90
반응형

간단한 브루트포스 알고리즘 or 다이나믹 프로그래밍 문제이다.

브루트포스 알고리즘 풀이

a, b, c, n = map(int, input().split())
res = 0
for i in range(0, n+1, a):
    for j in range(0, n-i+1, b):
        for k in range(0, n-i-j+1, c):
            if i+j+k == n:
                res = 1
print(res)

다이나믹 프로그래밍 풀이

a, b, c, n = map(int, input().split())
li = [a, b, c]
dp = [0]*(n+1)
dp[0] = 1
for i in range(1, n+1):
    for t in li:
        if i-t >= 0 and dp[i-t]:
            dp[i] = 1
print(dp[n])
728x90
반응형
728x90
반응형

기본적인 다이나믹 프로그래밍 문제이다. 현재 포도주를 마시지 않는 경우, 앞에 포도주를 마시고 현재 포도주를

마시는 경우, 앞에 포도주를 마시지 않고 현재 포도주를 마시는 경우로 총 세 가지를 고려해주면 된다.

-> dp[i] = max(dp[i-1], dp[i-3]+li[i-1]+li[i], dp[i-2]+li[i])

n = int(input())
li = [0] + [int(input()) for _ in range(n)]
dp = [0]*(n+1)
dp[1] = li[1]
if n > 1:
    dp[2] = li[1] + li[2]
for i in range(3, n+1):
    dp[i] = max(dp[i-1], dp[i-3]+li[i-1]+li[i], dp[i-2]+li[i])
print(max(dp))
728x90
반응형
728x90
반응형

다이나믹 프로그래밍 or 그래프 탐색 문제이다.

다이나믹 프로그래밍 풀이

N = int(input())
dp = [[0, []] for _ in range(N+1)]
dp[1][0] = 0
dp[1][1] = [1]
for i in range(2, N+1):
    dp[i][0] = dp[i-1][0] + 1
    dp[i][1] = dp[i-1][1] + [i]
    if i%2 == 0 and dp[i//2][0]+1 < dp[i][0]:
        dp[i][0] = dp[i//2][0] + 1
        dp[i][1] = dp[i//2][1] + [i]
    if i%3 == 0 and dp[i//3][0]+1 < dp[i][0]:
        dp[i][0] = dp[i//3][0] + 1
        dp[i][1] = dp[i//3][1] + [i]
print(dp[-1][0])
print(*dp[-1][1][::-1])

 

그래프 탐색(BFS) 풀이

입력이 1일 때만 주의해서 잘 처리해주면 된다.

from collections import deque

def bfs(node, dp):
    q = deque()
    q.append((node, dp))
    while q:
        node, dp = q.popleft()
        for n in [node+1, node*2, node*3]:
            if n <= N and check[n] == 0:
                if n == N:
                    return check[node]+1, dp+[n]
                q.append((n, dp+[n]))
                check[n] = check[node]+1

N = int(input())
if N == 1:
    print(0)
    print(1)
else:
    check = [0]*(N+1)
    cnt, dp = bfs(1, [1])
    print(cnt)
    print(*dp[::-1])
728x90
반응형
728x90
반응형

기본적인 백트래킹 문제이다.

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

N, M = map(int, input().split())
check = [0]*N
li = []        
dfs(0)
728x90
반응형

+ Recent posts