728x90 반응형 Dynamic Programming11 [백준/python] 1463 - 1로 만들기(DP) 문제: https://www.acmicpc.net/problem/1463 사용 알고리즘: DP 할 수 있는 연산- 1 빼기- 2로 나누기- 3으로 나누기 나는 dp 문제를 풀 때 잘 모르겠으면 손으로 써가면서 규칙을 찾아 점화식을 쓰는 편인데 이번 문제도 쓰면서 풀다보니 규칙이 보였다. dp[1] = 0 -> 1 은 아무 연산을 하지 않아도 1 이기 때문에 연산 횟수는 0dp[2] = 1 -> 2 는 2-1 또는 2//2 를 해서 1 로 만들 수 있고 최소 연산 횟수는 1dp[3] = 1 -> 3 은 3//3 을 해서 1로 만들 수 있고 최소 연산 횟수는 1 dp[4]: 4 -> 2 -> 1dp[5]: 5 -> 4 -> 2 -> 1dp[6]: 6 -> 2 -> 1dp[7]: 7 -> 6 -> 2-> .. 2024. 5. 20. [백준/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. [Beakjoon/백준] 2579 파이썬 문제: https://www.acmicpc.net/problem/2579 사용 알고리즘: DP - 1번째 계단에 올라가는 법은 1가지 밖에 없음dp[1] = stairs[1] - 2번째 계단에 올라가는 법1번째 계단 -> 2번째 계단 : dp[2] = stairs[1] + stairs[2] -> 무조건 최댓값이 더 큼2번째 계단: dp[2] = stairs[2] - 3번째 계단에 올라가는 법1번째 계단 -> 3번째 계단: dp[3] = stairs[1] + stairs[3] 2번째 계단 -> 3번째 계단: dp[3] = stairs[2] + stairs[3]이 경우에는 계단에 부여된 점수에 따라 상황이 달라질 수 있음-> dp[3] = max(stairs[1] + stairs[3], stairs[2.. 2024. 5. 14. 이전 1 2 3 다음 728x90 반응형
