Algorithm/Dynamic Programming69 [파이썬] 프로그래머스 : 연속 펄스 부분 수열의 합 (레벨3) [파이썬] 프로그래머스 : 연속 펄스 부분 수열의 합 (레벨3)https://school.programmers.co.kr/learn/courses/30/lessons/161988풀이방향성 생각입력보고 $O(N)$으로 비벼야겠다고 생각state는 1이 곱해졌는지, -1으로 곱해졌는지 2가지로 나뉘길래 2차원 dp만들고 $O(N)$으로 순회dp배열에는 현재 1 혹은 -1이 곱해졌을 때 부분 수열의 합의 최대값을 기록한다dp배열에는 최대값을 끝까지 가지고 있지 않다 (다음 위치에는 부분 수열의 합이 작아질수도) -> max(dp[0]), max(dp[1]) 비교 전체코드def solution(arr): N = len(arr) dp = [[0]*N for _ in range(2)] dp[0][0.. 2025. 3. 23. [파이썬, 자바] 백준 12865 : 평범한 배낭 (골드5) [파이썬, 자바] 백준 12865 : 평범한 배낭 (골드5)https://www.acmicpc.net/problem/12865풀이방향성 생각냅색 기본문제state는 n번째 가방 / 무게 k이다.현재 노드가 n,k이면 물건을 가방에 담기 전 무게는 k-w이다.또한, 가방에 물건을 담지 못하는 경우도 계속해서 업데이트 해준다. 파이썬import sysinput = lambda : sys.stdin.readline().rstrip()N,K = map(int, input().split())arr = [None] + [tuple(map(int, input().split())) for _ in range(N)]dp = [[0]*(K+1) for _ in range(N+1)]for n in range(N): w.. 2025. 2. 9. [파이썬, 자바] 백준 2240 : 자두나무 (골드5) [파이썬, 자바] 백준 2240 : 자두나무 (골드5)https://www.acmicpc.net/problem/2240풀이방향성 생각바텀업 DP 정석state는 3개로 구분된다.현재 위치 n, 현재 나무 위치 l, 이동 횟수 kdp[k][l][n]으로 3차원 DP 테이블 작성n 에서 n+1로 넘어갈 때 l을 바꿀지 안바꿀지에 따라서 k값 증가유무가 결정된다.이동하지 않으면 l도 고정이고, 이동하면 k가 증가하면서 l은 토글된다.k값이 K와 같으면 다음 K+1은 없으므로, 인덱스 에러를 방지해주는 조건문추가.# 기본적으로 다음 노드에 도착하면 사과 유무로 + 1 해주기# 옆 나무로 이동하는 경우 k+1되며 l은 toggle된다.dp[k+1][l][n+1] = max(dp[k+1][l][n], dp[k][l.. 2025. 2. 9. [파이썬] 백준 2011 : 암호코드 (골드5) [파이썬] 백준 2011 : 암호코드 (골드5)https://www.acmicpc.net/problem/2011풀이방향성 생각바텀업으로 state 나눠서 전 노드/전전 노드에서 들어오는 방식으로 풀기탑다운으로 조건에 맞는 경우에만 탐색 진행하기 전체코드import syssys.setrecursionlimit(10**6)string = input()L = len(string)dp = [-1]*LMOD = 1000000def dfs(x): if x == L: return 1 if dp[x] != -1: return dp[x] result = 0 if string[x] != '0': result += dfs(x+1) if x+1 코멘트.탑다운 :.. 2024. 12. 31. 이전 1 2 3 4 5 6 ··· 18 다음
