For Programmer

import sys input = sys.stdin.readline N = int(input()) dp = [[0, 0, 0], [0, 0, 0]] dp2 = [[1e6, 1e6, 1e6], [0, 0, 0]] idx = 0 for i in range(1, N + 1): arr = list(map(int, input().split())) for j in range(3): dp2[idx][j] = 1e6 for k in range(3): if abs(j - k) >= 2: continue dp[idx][j] = max(dp[idx][j], dp[not idx][k] + arr[j]) dp2[idx][j] = min(dp2[idx][j], dp2[not idx][k] + arr[j]) idx = not id..

a = '#' + input() b = '#' + input() dp = [[0 for _ in range(len(b) + 1)] for _ in range(len(a) + 1)] ''' 단순히 생각해서 2개의 문자열에 뒤에 같은 문자가 들어오면 공통 부분 문자열의 개수가 1개씩 증가한다는 개념을 이용해서 DP를 구하면 쉽다 ''' for i in range(1, len(a)): for j in range(1, len(b)): if a[i] == b[j]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) print(dp[len(a) - 1][len(b) - 1])

정말 어려운 문제이다.... 이분탐색에 dp개념을 추가해야 해결할 수 있다. 자세한 설명은 생략한다.. python tutor로 dp배열 v가 어떻게 변하는지 확인해보기 바란다. N = int(input()) arr = list(map(int, input().split())) v = [-100000] for i in range(N): s = 0 e = len(v) - 1 idx = 0 while s

DP개념 익히기 좋은 문제이나 사실 3차원 DP를 처음부터 생각하기란 쉽지 않다.. DP의 형태를 보면 depth -> 현재 이어붙인 숫자의 개수, cnt -> 인접한 비트의 개수, cur -> 현재의 비트(0,1) 형태로 되어있다.여기서 DP개념을 이용하자면 어느 한지점(depth) 에서 내가 현재 구한 숫자의 개수(cnt)를 가지고 현재의 비트(cur)에서 구할 수 있는 개수를 저장해놓으면 어차피 다른 재귀가 해당 지점에 도착했을 시 이미 구한 개수를 이용하면 된다. 이러한 개념이 DP인데 다음의 코드를 잘 분석하면 된다. def dfs(depth, cnt, cur): if depth == N: if cnt == K: return 1 else: return 0 if dp[depth][cnt][cur]..

후.... 하루종일 뚫어져라봐도 가장 긴 증가 부분수열의 개수를 구하라는 문제인지를 몰랐다.. 골드 5라고 하는데 아마 LIS가 웰노운이라서 골드 5이지 문제만 보고 LIS 알고리즘을 생각하는건 쉽지 않다..... 어찌됐든 문제의 접근방식은 전봇대 번호를 기준으로 정렬한 후 연결된 번호들을 기준으로 가장 긴 증가하는 부분수열의 개수를 구한 다음 전체의 전봇대 개수에서 빼주면 된다. N = int(input()) arr = [list(map(int, input().split())) for _ in range(N)] arr.sort(key=lambda x: (x[0])) arr += [[0, 0]] dp = [[-1] * (N + 1) for _ in range(N + 1)] def dfs(cur, pre)..

현재 고른 위치와 전에 고른 위치를 dp에 저장해서 다음번에 도착시 해당 dp에 저장된 값을 리턴하도록 코드를 구현했다. import sys sys.setrecursionlimit(10000) N = int(input()) arr = list(map(int, input().split())) + [0] dp = [[-1] * (N + 1) for _ in range(N + 1)] def recur(cur, pre): if cur >= N: return 0 if dp[cur][pre] != -1: return dp[cur][pre] if arr[cur] > arr[pre]: dp[cur][pre] = max(recur(cur + 1, cur) + arr[cur], recur(cur + 1, pre)) els..

def win(p, q): # 이미 계산된 적 있으면 해당 결과를 리턴 if dp[p][q] >= 0: return dp[p][q] # p에 있는 구슬들을 우선 뺀다. for i in range(3): if b[i]

이 문제의 핵심은 여러 경로들을 지나간 횟수와 그 때 현재의 노드를 기준으로 dp[현재의 노드][지나간 횟수]를 저장하는 것이다. 3을 기준으로 본다면 1 -> 2 -> 3 -> 4 ... 2 -> 1 -> 4 -> 3 -> 5 ... 4 -> 2 -> 3 -> 6.... 과 같이 3이 3번째인 수많은 경로가 나온다고 할 때 3번째에 3의 정점을 지나가는 경우의 수는 미리 구해놓으면 다음번에 지나갈 때 굳이 또 검사를 안해도 된다는 것이다. 또한 10^9 + 7을 계산할 때마다 나누어서 저장해주어야 한다는 점 또한 잘 체크해야 한다. import sys def dfs(cur, cnt): if cnt > 7: return 1 if dp[cur][cnt] != -1: return dp[cur][cnt] dp..