dp

[DP] BOJ 1509 펠린드롬 분할

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 import sys sys.setrecursionlimit(10 ** 8) input = lambda: sys.stdin.readline().rstrip() arr = input() N = len(arr) p = [[0] * N for _ in range(N)] dp = [N] * (N + 1) for i in range(N): # 1개짜리 문자열 p[i][i] = 1 for i in range(N - 1): # 2개짜리 문자열 if arr[i] == arr[i + 1]: p[i][i + 1] = 1 for interval in range(..

[DP] BOJ 10942 펠린드롬?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 import sys input = sys.stdin.readline N = int(input()) + 1 arr = [0] + list(map(int, input().split())) M = int(input()) dp = [[0] * N for _ in range(N)] # dp table initialization for i in range(N): dp[i][i] = 1 for i in range(N-1): if arr[i] == arr[i + 1]: dp[i][i + 1] = 1 for interval in range(2, N): # 간격 설정 for start in range(N-..

[DP] 프로그래머스 - 카운트다운

https://school.programmers.co.kr/learn/courses/30/lessons/131129 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 # dp[i][0]은 최소가 되어야 하고 dp[i][1]은 최대가 되어야 하는 문제 def solution(target): dp = [[1e9, 0] for _ in range(target+1)] dp[0] = [0,0] # dp 초기화 # scores 리스트 구성 scores = [50] for i in range(1, 21): scores.extend([i, i*2, i*3]) scores.sort() # single, b..

[DP] BOJ 2208 보석줍기

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 import sys input = sys.stdin.readline ''' 부분 연속합 관련 문제 -> dp 로 풀이 가능 1. 각 구간에 대한 구간합 구하기 -> [!] itertools.accumulate로도 풀 수 있음 2. M개 기준으로 최대가 되는 구간합 구하기. M개는 최소 기준이며 추가가 될 수 있도록 함 ''' N, M = map(int, input().split()) jewels = [int(input()) for _ in range(N)] accum = [0] * N # 누적합 for i in range(N): accum[i] = accum[i-1] + jewels..

[DP] BOJ 15486 퇴사 2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 import sys input = sys.stdin.readline N = int(input()) arr = [list(map(int, input().split())) for _ in range(N)] dp = [0] * (N + 1) for i, (t, p) in enumerate(arr, 1): dp[i] = max(dp[i-1], dp[i]) # 누적값 vs n일차 상담값 if i + t - 1 > N: continue # 상담 날짜가 퇴사날짜를 넘을 경우 해당 상담은 불가 dp[i + t - 1] = max(dp[i - 1] + p, dp[i + t -1]) # 새 상담 날짜 추가 print(dp[-1]) Colored by C..

[DFS X DP] BOJ 17070 파이프 옮기기 1

1차 시도 : DFS로 문제 풀이 -> 시간 초과 발생 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 import sys from collections import deque input = sys.stdin.readline # DELTAS = ((0, 1), (1, 0), (1, 1)) WIDTH = (('w', 1, 0), ('d', 1, 1)) HEIGHT = (('h', 0, 1), ('d', 1, 1)) DIAGONAL = (('w', 1, 0), ('h', 0, 1), ('d', 1, 1)) DELTAS_DICT = {'w': WIDTH, ..

[DP] BOJ 9655 돌 게임

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 import sys input = sys.stdin.readline N = int(input()) dp = [100001] * (N+1) if N > 2: dp[1] = 1 dp[2] = 2 for i in range(3, N+1): dp[i] = min(dp[i-1], dp[i-3]) + 1 elif N == 2: dp[2] = 2 else: dp[1] = 1 if dp[N] % 2 == 0: print("CY") else: print("SK") cs

[DP] BOJ 2294 동전 2

https://seclab-j.tistory.com/76 2293 문제의 응용버전. 기존 문제에서는 dp[i-coin]을 모두 더하는 방향으로 진행하였다면 해당 문제는 그중 가장 작은 횟수를 선택하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 import sys input = sys.stdin.readline N, K = map(int, input().split()) arr = [int(input()) for _ in range(N)] dp = [100001] * (100001) dp[0] = 0 for coin in arr: dp[coin] = 1 for i in range(coin, K+1): dp[i] = min(dp[i-coin] + 1, dp[i]) # 가장 작..

[DP] BOJ 2133 타일 채우기

보호되어 있는 글입니다.

[DP] BOJ 11048 이동하기

1 2 3 4 5 6 7 8 9 10 11 12 13 14 import sys input = sys.stdin.readline N, M = map(int, input().split()) arr = [[0] * (M+1)] + [[0] + list(map(int, input().split())) + [0] for _ in range(N)] + [[0] * (M+1)] dp = [[0] * (M+1) for _ in range(N+1)] for i in range(1, N+1): for j in range(1, M+1): dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + arr[i][j] print(dp[N][M]) Colored by Color Scripte..

[DP] BOJ 11722 가장 긴 감소하는 부분 수열

https://seclab-j.tistory.com/57 [DP] BOJ 11053 가장 긴 증가하는 부분 수열 import sys input = sys.stdin.readline N = int(input()) arr = list(map(int, input().split())) dp = [1] * N # 처음 시작할 때를 대비해서 1로 초기화 for i in range(1, N): for j in range(i): if arr[j] seclab-j.tistory.com 와 사실상 동일한 문제. 푸는 방식만 반대로 풀면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 import sys input = sys.stdin.readline N = int(input()) arr = list(ma..

[DP] BOJ 11660 구간합 구하기5

import sys input = sys.stdin.readline N, M = map(int, input().split()) arr = [[0] * (N+2)] + [[0]+list(map(int, input().split()))+[0] for _ in range(N)] + [[0] * (N+2)] points = [list(map(int, input().split())) for _ in range(M)] dp = [[0] * (N+2) for _ in range(N+2)] for i in range(1, N+1): for j in range(1, N+1): dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + arr[i][j] for x1, y1, x2, y2 ..