Algorithm/Dynamic Programming69 [파이썬] 백준 13398 : 연속합 2 (골드5) [파이썬] 백준 13398 : 연속합 2 (골드5)[백준 13398 : 연속합 2](13398번: 연속합 2)풀이방향성 생각제거할 노드를 선택/미선택 2개 상태로 나누어서 접근한다.$2*N$ 크기 배열로 만들고 dp 테이블 바텀업으로 업데이트.코드N = int(input())arr = list(map(int,input().split()))INF = float('inf')dp = [[-INF]*N for _ in range(2)]dp[0][0] = arr[0]for i in range(N-1): dp[0][i+1] = max(dp[0][i]+arr[i+1],arr[i+1]) dp[1][i+1] = max(dp[0][i],dp[1][i]+arr[i+1])print(max(max(dp[0]),max.. 2025. 5. 18. [파이썬] 백준 2225 : 합분해 (골드5) [파이썬] 백준 2225 : 합분해 (골드5)백준 2225 : 합분해 (골드5)풀이방향성 생각숫자 N을 만드는데 K개의 숫자를 쓰는 형태.숫자 N-X를 만드는데 K-1개의 숫자를 쓰는 부분 구조를 가지고 있다.DP를 통해서 계산 최적화시키기.$O(N*M)$이 굉장히 작은 경우라 바텀업이 빠르지만 탑다운으로 풀이.$dp[remain][number]$의 형태로 dp 배열을 작성한다.타 언어의 경우, 오버플로우의 위험 때문에 매 result에서 MOD 연산을 해줘야 할 수도 있는데 파이썬이라서 마지막 한 번만 MOD를 해주면 된다.코드N,K = map(int,input().split())MOD = 10**9dp = [[-1]*(N+1) for _ in range(K+1)]def dfs(x,cnt): # .. 2025. 5. 11. [파이썬] 백준 2293 : 동전1 (골드4) [파이썬] 백준 2293 : 동전1 (골드4)https://www.acmicpc.net/problem/2293풀이방향성 생각unbounded knapsack현재 선택한 동전으로 가방을 모두 채운다.다음 선택한 동전으로 가방을 모두 채운다. 반복현재 value에서 gain을 뺐을 때 음수가 오는 곳에서 인덱스 에러만 처리해주며 된다. 전체코드import syssys.setrecursionlimit(10**6)N,K = map(int,input().split())arr = [int(input()) for _ in range(N)]dp = [[-1]*(K+1) for _ in range(N)]def dfs(idx,x): # 기저조건 if not x: return 1 # 마지막 동전.. 2025. 4. 15. [파이썬] 백준 2613 : 숫자구슬 (골드2) [파이썬] 백준 2613 : 숫자구슬 (골드2)https://www.acmicpc.net/problem/2613풀이방향성 생각현재 배열에서 분할 횟수가 remain번 남았을 때, [s,e] 구간을 [s,m] [s,m+1]로 분할하기.배열 크기는 N^3이라 2700만이다.혹은 2차원으로 줄여서 풀이 가능.group을 g개로 분할했을 때, 인덱스 x까지 탐색했을때 그룹의 최대값을 dp에 저장역추적은 LCS에서 역추적하는 것 처럼 추적해주기.최소값을 갱신할 때, 이전 인덱스 변화를 저장해주기. 파이썬N,M = map(int,input().split())arr = list(map(int,input().split()))INF = float('inf')cumsum = [0]for a in arr: cumsum.. 2025. 4. 10. 이전 1 2 3 4 ··· 18 다음
