전체 글251 백준 2156번: 포도주 시식 (Python / DP) 백준 2156번: 포도주 시식 (Python / DP)문제 링크https://www.acmicpc.net/problem/2156문제 설명N개의 포도주 잔이 일렬로 놓여 있고, 각 잔에는 일정량의 포도주가 들어 있다.포도주를 마실 때 연속으로 3잔은 마실 수 없다는 제약 조건이 있다.가장 많은 양의 포도주를 마시기 위해서는 어떤 잔을 선택해야 할까?⸻접근 방식 (DP)이 문제는 DP(동적 계획법) 으로 해결할 수 있습니다.우선 dp[i]를 i번째 포도주까지 마셨을 때 마실 수 있는 최대 포도주 양이라고 정의해보자.고려해야 할 세 가지 경우 • dp[i-1]: i번째 포도주를 마시지 않은 경우 • dp[i-2] + wine[i]: i번째 포도주는 마시고, i-1번째는 건너뛴 경우 • dp[i-3] + win.. 2025. 5. 22. [백준 1912번] 연속합 – Python DP 풀이 [백준 1912번] 연속합 – Python DP 풀이https://www.acmicpc.net/problem/1912문제 설명N개의 정수로 이루어진 수열이 주어졌을 때, 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 값을 구하는 문제입니다. • 예제 입력10 10 -4 3 1 5 6 -35 12 21 -1 • 예제 출력33→ 위 입력에서 가장 큰 연속 부분합은 12 + 21 = 33입니다.⸻잘못된 접근: 투 포인터 방식처음에는 아래와 같은 방식도 떠오를 수 있습니다:# 누적합과 투 포인터로 최대값을 구해보려는 시도left, right = 0, n-1while left # 좌우 값을 제거하며 최대합 갱신하지만 이 문제는 모든 연속 구간을 탐색해야 하므로, 단순히 양끝에서 제외한다고 .. 2025. 5. 19. 백준 9461번 - 파도반 수열 (Python, DP) ⸻https://www.acmicpc.net/problem/9461백준 9461번 - 파도반 수열 (Python, DP)문제 설명정수 N이 주어졌을 때, 파도반 수열의 N번째 값을 구하는 문제입니다. 파도반 수열은 아래와 같은 규칙을 따릅니다:P(1) = 1P(2) = 1P(3) = 1P(4) = 2P(5) = 2P(6) = 3P(7) = 4P(8) = 5P(9) = 7P(10) = 9...⸻문제 접근이 문제는 점화식을 세우고, 이를 이용해 DP 배열을 채워 나가는 방식으로 해결할 수 있습니다. 주어진 수열을 분석해보면 다음과 같은 규칙을 도출할 수 있습니다.점화식 도출dp[n] = dp[n-1] + dp[n-5]즉, n번째 파도반 수열 값은 n-1번째 값과 n-5번째 값을 더한 값과 같습니다.단, 이 .. 2025. 5. 16. 백준 1932번 - 정수 삼각형 (Python / DP) 백준 1932번 - 정수 삼각형 (Python / DP)https://www.acmicpc.net/status?user_id=dahun428&problem_id=1932&from_mine=1문제 설명N층의 정수 삼각형이 주어졌을 때, 위에서 아래로 내려오며 숫자를 하나씩 선택하여 합이 최대가 되는 경로를 찾는 문제입니다. • 각 칸에서는 바로 아래 또는 오른쪽 아래로만 이동할 수 있습니다. • 입력으로는 삼각형의 높이 n이 주어지고, 각 층의 정수들이 한 줄씩 입력됩니다.⸻예제 입력573 88 1 02 7 4 44 5 2 6 5예제 출력30예: 7 → 3 → 8 → 7 → 5 = 30이 최대 경로입니다.⸻문제 접근이 문제는 대표적인 Bottom-up 방식의 DP 문제입니다. • dp[i][j]를 i층 j.. 2025. 5. 14. 이전 1 2 3 4 ··· 63 다음