알고리즘/DynamicProgramming9 포도주 시식 ( 백준 2156 ) https://www.acmicpc.net/problem/2156 * 포도주를 최대한 많이 마셔야 하는 상황* 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 함* 연속으로 놓여 있는 3잔을 모두 마실 수는 없음* 위 조건에 맞추어서 1-n까지의 번호가 붙어 있는 n개의 포도주 잔이 존재하고 최대한 많은 양을 마셔야 함 * 순서대로 마셔야 하니까 정렬, 그리디 보다는 dp라고 생각했다* 문제에 안마셔야 하는 법은 안적혀 있어서 무조건 마셔야 하는 경우만 생각했다.( 좀 이상한데...? )* 그러면 아래와 같은 점화식이 도출된다.* 초기값-dp[0] : 첫번째 포도주 시식-dp[1] : 첫번째 포도주 + 두번째 포도주 시식-dp[2] : 첫번째 포도.. 2025. 2. 26. 1로 만들기 ( 백준 1463 ) https://www.acmicpc.net/problem/1463 * dp 알고리즘을 활용하는 문제* 순차적으로 증가하는 수열이 아니라서 어떻게 풀어야할지 고민함* dp[] 배열을 사용할때 3가지 연산이 존재함* %2, %3을 해서 나누어 떨어질때 하는 연산들은 2의배수 3의배수 일때만 가능함* -1하는 연산은 어떤 값이든 간에 가능하기 때문에 제일 먼저 연산 시작* dp[i]-1 = dp[i-1] 해서 1되는지 보지만 dp[i] 값을 보기위해 이항해서 dp[i] = dp[i-1] + 1 식을 활용한다* dp[i] = dp[i-1] + 1과 2로 나누어 떨어지면 dp[i/2], 3으로 나누어 떨어지면 dp[i/3] 비교해 최소값으로 갱신* 최종 input 배열에 있는 값을 출력 * 아이패드에 끄적여 보.. 2025. 2. 24. 1, 2, 3 더하기 백준 9095 ( dp ) https://www.acmicpc.net/problem/9095 dp를 활용한 문제.처음에는 덧셈 결과를 가지고 점화식을 세우는줄 알았는데,합이 1일때 경우의수합이 2일때 경우의수합이 3일때 경우의수 ,,,, 이렇게 해서 dp[i] = dp[i-3]+dp[i-2]+dp[i-3] 점화식을 세워서for 루프를 한번만 돌려서 O(N) 시간 복잡도가 걸린다. 이렇게 규칙을 발견하면 i-1, i-2, i-3 더한 값이 i 에 할당되는 점화식을 세울 수 있다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class onetwothree { sta.. 2025. 2. 17. 이전 1 2 다음
