728x90 반응형 실버12 [백준/Python] 11660 구간 합 구하기 5 문제: https://www.acmicpc.net/problem/11660 사용 알고리즘: DP, 누적합 입력받기import sysinput = sys.stdin.readlineN, M = map(int, input().split())arr = [[0] * (N+1)]for i in range(N): arr.append([0] + list(map(int, input().split()))) 위와 같은 모양으로 사용하기 위해 배열의 0 번째 열과 행을 모두 0 으로 초기화 시켰다. ( 배열의 0 번째 열과 행을 0으로 초기화 시켜놓지 않으면 dp 값을 채울 때 인덱스 에러가 난다 ) dp 값 채우기 dp 의 값은 (i,j) 의 총 누적합이다. 인덱스 1 부터 사용하기 위해 (N+1)*(N+1) .. 2024. 7. 13. [백준/python] 2156 - 포도주 시식 문제: https://www.acmicpc.net/problem/2156 사용 알고리즘: DP n 개의 포도주를 처음부터 차례로 돌면서 먹을지 안 먹을지 결정 - i 번째 포도주를 먹지 않는다 -> dp[i-1]- i 번째 포도주를 먹는다i-1 번째 포도주를 먹는 경우 (직전 포도주를 먹는 경우) -> dp[i] = dp[i-3] + wine[i-1] + wine[i]i-2 번째 포도주를 먹는 경우 (전전 포도주를 먹는 경우) -> dp[i] = dp[i-2] + wine[i] 점화식: dp[i] = max(진전 포도주를 먹는 경우, 안먹는 경우, 전전 포도주를 먹는 경우) (i > 2) -> dp[i] = max(dp[i-3] + wine[i-1] + wine[i], dp[i-1], dp[i-2].. 2024. 5. 20. 이전 1 다음 728x90 반응형
