DP

📖 문제 https://www.acmicpc.net/problem/1958   💡  풀이 방식• LCS문자열이 3개이므로, 3차원 DP로 LCS 길이를 구하면 된다. - 3중 for문을 이용해 i == j == k인 지점을 찾아 갯수를 센다.(i, j, k) = max( (i-1, j, k), max( (i, j-1, k), (i, j, k-1) ) )   🔺 코드123456789101112131415161718192021222324252627282930313233import java.util.*;import java.io.*; public class Main {    static int[][][] dp;    // 3차원 DP    static char[] A,B,C;        public s..

📖 문제 https://www.acmicpc.net/problem/14002   💡  풀이 방식• LIS (DP) LIS 배열을 만든다.이 때 String 배열을 숫자의 수만큼 만들고, 최장 길이 수열이 만들어졌을 때 수열 정보를 업데이트한다.   🔺 코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950import java.util.*;import java.io.*; public class Main {    static int N;    static int[] A, dp;    static String[] str;        public static void main(String[] ..

📖 문제  프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr   💡  풀이 방식• DP[점화식]dp[i] = Math.max(dp[i-1], dp[i-2] + sticker[i])   0번째 스티커를 뗐느냐/안 뗐느냐 여부에 따라 숫자의 합을 다르게 구한다.  1) 0번째 스티커를 뗀 경우, 1번째와 마지막 스티커는 뗄 수 없다.// dp 배열 초기값dp1[0] = sticker[0];dp1[1] = sticker[0];   2) 0번째 스티커를 떼지 않은 경우, 마지막을 뜯을 수 있다.// dp 배열 초기값dp2[0] = 0;dp2[1] = sticker[..

📖 문제  프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr    💡  풀이 방식• BFS + DP4가지 방향에서 오는 방향 별 최소 비용을 저장하기 위해 방향까지 합친 3차원 배열을 사용하는 것이 포인트!이 때, 단순 bfs로만 탐색하면 각 방향마다 달라지는 최소 비용을 지나칠 수 있으므로 dp (메모이제이션)을 사용한다. - 4방향 탐색을 할 때, 처음 실행하거나 방향이 바뀌지 않은 경우에는 현재 비용에서 +100원만큼, 방향이 바뀐 경우에는 +600원만큼 이동하도록 한다. (방향 전환하느라 +500, 직진하느라 +100 한 번 더 하므로)int next..

📖 문제 https://www.acmicpc.net/problem/12872  💡  풀이 방식• DPDP[ i ][ j ] : i개의 음악을 플레이리스트에 넣고, j개의 음악 종류를 사용했을 때의 경우의 수 어떤 집합에서 아무거나 하나를 놓으면 된다= 어떤 집합의 원소의 수를 곱한다  음악은 플리(플레이리스트)에 넣었는지 여부에 따라 2가지 종류로 나눌 수 있다. 1) 플리에 넣지 않은 음악인 경우  - 아직 플리에 넣지 않았으므로, 같은 노래 사이에 M개의 곡이 있어야 한다는 2번 조건은 고려할 필요가 없다.  - 대신 이전 모든 경우의 수들에 추가될 수 있으므로 아래와 같은 점화식이 도출된다.dp[musicNum][savedMusicNum] += dp[musicNum - 1][savedMusicN..

📖 문제 https://www.acmicpc.net/problem/11066   💡  풀이 방식• DPDP[ from ][ to ] : from ~ to번째 챕터를 합쳤을 때 최솟값 3중 반복문을 통해 DP[1][2] ~ DP[1][K]까지의 최소 비용 값을 구한다.  private static void solve(int k) { for(int to = 2 ; to = 1 ; from--) { // 출발지 (어디서부터 묶을건지) dp[from][to] = Integer.MAX_VALUE; for(int x = from ; x    🔺 코드1234567891011121314151617181920212223242526272829303132333435363..

📖 문제  2225번: 합분해첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.www.acmicpc.net   💡  풀이 방식• DPDP[K][N] : 숫자 K개를 사용해 N을 만들 수 있는 경우의 수 1. 초기화숫자 K개로 0을 만드는 경우의 수는 항상 1개이다.for(int i = 1 ; i   2. 점화식 찾기표를 그리다 보면, 한 칸은 해당 칸의 위쪽 값과 왼쪽 값을 합한 값으로 채우는 규칙을 발견할 수 있다.그렇기 떄문에 점화식이 아래와 같이 성립된다. for(int i = 1 ; i     🔺 코드1234567891011121314151617181920212223242526272829import java.io.*; public class Main {    static f..

📖 문제  15990번: 1, 2, 3 더하기 5각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.www.acmicpc.net   💡  풀이 방식• DP 같은 숫자가 2번 이상 연달아 나오면 안 된다는 조건이 있으므로,마지막 숫자를 기준으로 갯수를 센다.  예) 41 = dp[1][1] (1)2 = dp[2][2] (2)3 = dp[3][1] (2,1) + dp[3][2] (1,2) + dp[3][3] (3)4 = dp[4][1] + dp[4][2] + dp[4][3]   = (dp[3][2] + dp[3][3]) + (dp[2][1] + dp[2][3]) + (dp[1][2] + dp..

📖 문제 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 💡 풀이 방식 • DP dp[ i ][ j ] = k ⇒ 1~i번째 집까지 칠하고 i번째 집은 j색으로 칠했을 때의 최소 비용은 k 1. 첫 집에 칠할 색 k를 정한다. 그러고 나면 나머지 색으로는 첫 집을 칠할 수 없으므로 나머지 칸들은 최댓값으로 설정한다. (0: 빨강 / 1: 초록 / 2: 파랑) → dp[1][0] : 첫 집을 빨간색으로 칠함. 나머지 dp[1][1] = dp[1][2] = INF → dp[1][1] :..