✅ 문제https://www.acmicpc.net/problem/17484✅ 분류DP (다이나믹 프로그래밍)✅ 공부한 내용진우가 지구에서 달까지 높이마다 정해진 방향으로 이동할 때, 비용의 최솟값을 구하는 문제이다. 처음에는 높이마다 정해진 방향으로 이동하므로, 계층에 따른 모든 경우의 수를 완전탐색하는 DFS 알고리즘을 떠올렸다. 그러다가 문제가 탐색(재귀호출)으로 어떤 조합을 찾기보다는 최적해를 구하는 문제이므로, 메모리제이션을 활용한 DP 풀이가 더 적합하다는 생각으로 바뀌었다. 이동에는 3가지 경우가 있다. 1) 좌측 아래로 대각선 이동2) 아래로 이동3) 우측 아래로 대각선 이동 7번 노드로 이동하는 경우는 3가지가 있다. 1) 좌측 아래로 대각선 이동 ( 4번 )2) 아래로 이동 ( 5번 ..

✅ 문제https://www.acmicpc.net/problem/2156 ✅ 분류DP (다이나믹 프로그래밍)✅ 공부한 내용- 문제 요약총 n개의 포도주 잔이 일렬로 있다.한 번 마시면 모두 마셔야 하고, 마신 후에는 다음 잔으로 무조건 이동.3잔 연속 마시는 건 불가능.마실 수 있는 최대 포도주 양을 구해야 함.- 풀이 로직DP 배열 정의dp[i] = i번째 포도주까지 마실 수 있는 최대 양점화식 구성 (3가지 상황 존재)문제조건에서 연속으로 3잔을 마시면 안되기에wine[i-2], wine[i-1], wine[i]이 세 잔을 모두 마시는 경우는 안된다.i번째 포도주를 마시는 경우는 2가지 상황- (i - 2) 번째를 건너뛰고 (i - 1) 번째와 i번째를 연속으로 마신 경우:dp[i - 3] + win..

항해99 클럽 코테 스터디 2일차 TIL - 자바 미들러 4/1 (화요일)https://www.acmicpc.net/problem/14495✅ 문제📌  접근방법처음엔 막연히 재귀함수를 이용하였지만 시간복잡도가 O(2^N)이라 시간 초과로 런타임 오류가 났다.이를 해결하려면 메모이제이션(DP) 또는 반복문을 사용한 동적 계획법을 사용해야한다. -> O(N)또한, 문제조건에서 n이 116까지 입력받는데 f(116)은 int의 범위를 넘기 때문에 long을 써야했다. 런타임 오류 (오답)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { public stati..