DP (4) 썸네일형 리스트형 백준 13907번(JAVA)-세금 2차원 DP를 활용한 다익스트라 문제이 import java.util.*; import java.io.*; class Node implements Comparable { int v; int w; int c; Node(int v,int w,int c) { this.v=v; this.w=w; this.c=c; } public int compareTo(Node o) { return w-o.w; } } public class Main { public static int[][] dp; public static int N; public static int S; public static int D; public static void main(String[] args) throws IOException{ // TODO.. 백준 17404번(JAVA) 골드이상의 DP문제는 3차원으로 DP배열을 구현해서 문제푸는것이 수월하다. 이 문제는 기존 RGB거리 문제에 조건을 하나 더 추가한것으로 2번째 인덱스에 첫번쨰집의 색깔을 지정해놓고 풀면된다. 기존 RGB문제와 3차원배열을 활용한 DP문제링크를 걸어둘테니 참고하면 이 문제를 푸는데 매우 도움이 될듯하다. www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 2021.05.08 - [백준 문제풀이(JAVA)/DP(다이나믹프로그래밍)] - 백준 .. 백준 1563번(JAVA) 3차원 DP로 해결하는 문제이다 골드 4이상부터는 대부분 3차원DP로 풀어야 하는 것 같다. int[][][][ dp=new int[N][2][3];으로 선언해주고 [][][]에서 첫번째는 날짜를 2번째는 지각을 한 상태이면 1, 아니면0, 마지막인덱스는 연속결석날짜를 의미한다. dp[4][1][2]는 4번째날 지각을 한상태에서 2번연속 결석을한 경우의수를 의미한다. 일단 만약 날짜가 1일이면 지각,결석,출석 한가지씩이어서 3을 출력하고 시스템종료 그다음 2틀째날에는 총 8가지 경우의수가 있다. 각각 맞게 설정해주고 bottom-up방식으로 구현하기 위해 for문을 i=2부터 실행해준다. 자세한 사항은 아래 소스코드를 보며 이해하자. 소스코드 import java.util.*; public class M.. 백준 1103번(JAVA) 이 문제는 DFS와 다이나믹프로그래밍을 모두 적용시켜야 하는 문제이다. DFS를 진행하는도중 만약 방문된곳을 한번 더 방문했다면 바로 -1을 출력하고 프로그램을 종료시켰다 왜?? 경로에 사이클이 생성되었다는 뜻이기 때문이다. DP배열은 단순히 해당 지점까지의 게임횟수를 의미한다. 그런데 만약 다음지점에서의 dp값이 10이다. 근데 현재 지점에서까지의 게임횟수는 5이면 다음지점으로 넘어갈 필요가 있는가? 답은 X다. 왜냐하면 우리는 최대게임횟수를 찾는것이기 때문이다. 위의 내용을 머리에 넣고 아래 소스코드를 보면 이해가 갈것이다. 소스코드 import java.io.*; import java.util.*; public class Main { public static int N; public static i.. 이전 1 다음