dynamic programing2 [C/C++] 백준 2156번 https://www.acmicpc.net/problem/2156 안녕하신지..오늘 풀어볼 문제는 백준 2156번, 실버1 문제이다. 두가지 조건을 만족하여 최대한 많은 양의 포도주를 먹는 프로그램을 만들어보자. 조건포도주는 최대 3잔까지 연속해서 마실 수 없다.이전 두 잔을 마셨다면, 현재 잔은 마실 수 없다. 점화식dp[i] : i번째 잔까지 마셨을 때의 최대 포도주 양.dp[i]=max(dp[i−1], dp[i−2]+wine[i], dp[i−3]+wine[i−1]+wine[i]) :dp[i−1] : 현재 잔을 마시지 않음.dp[i−2]+wine[i]: 한 잔 건너뛰고 현재 잔을 마심.dp[i−3]+wine[i−1]+wine[i]: 이전 잔과 현재 잔을 마심. 초기값 설정dp[1]=wine[1]d.. 2025. 1. 7. [C/C++] 백준 1463번 https://www.acmicpc.net/problem/1463 오늘 풀어볼 문제는 백준의 1463번 문제로 실버3 이다.정수 N이 주어졌을 때, 세 개의 연산을 적절히 사용해서 1을 만드는 프로그램을 만들어보자. 조건N은 1보다 크거나 같고, 10^6보다 작거나 같은 정수이다.연산을 하는 횟수의 최솟값을 출력한다.아이디어앞서 계산한 3가지 연산과 비교하여 가장 작은 것에 +1을 하여 구하는 방식으로 피보나치와 유사하다.초기값 설정N에 대한 연산 횟수의 최솟값을 dp(N)이라 하면N=1에 대한 dp(1)=0N=2인 값을 dp(2)=1N=3에 대한 dp(3)=1점화식따라서 dp(N)=min(dp(N/3),dp(N/2),dp(N-1))+1의 점화식을 갖게 된다.주의 ! 이때 N/3, N/2의 경우 각 나.. 2025. 1. 5. 이전 1 다음
