본문 바로가기

동적계획법4

[S1] 백준 2156 - 포도주 시식 (Python3) https://www.acmicpc.net/problem/2156풀이 아이디어DP 테이블을 사용하여 각 잔을 선택하는 경우와 선택하지 않는 경우 등을 나누어 최대값을 갱신한다.풀이👀포도주 잔이 1개일 때는 그대로 마시는 것이 최대값이므로 DP tabel의 0번째 인덱스의 초기값으로 설정한다.포도주 잔이 2개일 때는 첫 번째 잔과 두 번째 잔을 모두 마실 수 있으므로 두 잔의 양을 더한 값을 최대값으로 설정한다.포도주 잔이 3개 이상일 때는 연속으로 3잔을 마실 수 없기 때문에 경우를 나누어 최대값을 갱신한다.case1)  i번째 잔을 마시지 않는 경우: d[i-1]case2)  i-1번째 잔을 마시지 않고 i번째 잔을 마시는 경우: d[i-2] + wine[i]case3)  i-1번째 잔과 i번째 잔을.. 2024. 4. 28.
[S1] 백준 1149 - RGB거리 (Python3) https://www.acmicpc.net/problem/1149풀이 아이디어동적 계획법(DP, Dynamic Programming) 알고리즘으로 해결한다.각 집의 Red, Green, Blue 으로 색칠하는 비용이 주어졌을 때, 각 집을 칠할 때의 최소 비용을 계산한다. 이때 DP table을 이용해서 이전 집까지의 최소 비용을 가지고 현재 집을 칠할 때의 최소 비용을 구한다.풀이👀'현재 위치(i번째 집)에 대해서 전 후가 다른 색깔의 집이어야 한다.'는 조건이 걸려있다. 쉽게 풀어 설명하면 '연속해서 같은 색을 칠하지 말라'는 조건이다. 1. 첫 번째 집부터 마지막 집까지 반복하면서, 이전 까지의 최솟값으로 현재 집을 색칠할 때 최소 비용을 계산한다.코드🐱‍👓N = int(input())RGB .. 2024. 4. 28.
[G5] 백준 15486 - 퇴사 2 (Python3) https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 이 문제는 백준 퇴사(14501)와 같은 알고리즘으로 동작하는 문제이며, 이 해결방법으로도 14501번 문제를 통과할 수 있습니다. 해결방법 다이나믹 프로그래밍으로 해결했다. 이 문제는 마지막 날 부터 상담 건을 진행하면서 '이 날 근무하면 벌 수 있는 최대 금여'를 구하면 해결 할 수 있다. 풀이👀 문제에서 제공하는 예제로 풀이를 진행해보겠습니다. 1일(index:.. 2023. 11. 19.
[G5] 백준 9251 - LCS (python3) https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 해결방법 2차원 배열의 캐시값을 만들어 해결했다. - 백준 사이트의 [예제 입력 1] A C A Y K P [0, 0, 0, 0, 0, 0, 0] C [0, 0, 1, 1, 1, 1, 1] A [0, 1, 1, 2, 2, 2, 2] P [0, 1, 1, 2, 2, 2, 3] C [0, 1, 2, 2, 2, 2, 3] A [0, 1, 2, 3, 3, 3,.. 2023. 8. 20.

티스토리툴바