Dynamic Programming3 [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. [S1] 백준 1932 - 정수 삼각형 (Python3) https://www.acmicpc.net/problem/1932해결방법정수 삼각형의 맨 아래층부터 위층으로 올라간다. 각 행의 원소를 순회하면서, 현재 위치의 정수와 현재 위치의 왼쪽 아래 정수와 오른쪽 아래 정수 중 더 큰 값과의 합을 DP table에 저장한다. ( max(왼쪽아래 정수, 오른쪽아래 정수) + 현재위치 정수 )풀이👀주어진 정수 삼각형에서 아래층부터 위층으로 올라가며 각 행의 원소를 순회한다.각 행의 원소를 순회하면서 현재 위치의 정수에 다음 행(아래층)의 왼쪽 대각선 정수와 오른쪽 대각선 정수 중 더 큰 값을 더해가며 최대 합을 계산한다.모든 행을 순회하면서 이를 맨 위층까지 반복한다.최종적으로 맨 위층의 최대 합을 반환한다.코드🐱👓n = int(input())triangle.. 2024. 4. 27. 이전 1 다음