Hansel

DP문제는 점화식을 만드는게 중요하다. 첫번째 줄에 위치한 스티커의 경우 왼쪽 스티커의 점수와 대각선 아래 스티커의 점수 + 현재 스티커의 점수 중 큰 점수를 선택해야 하고, 두번째 줄에 위치한 스티커의 경우 왼쪽 스티커의 점수와 대각선 위 스티커의 점수 + 현재 스티커의 점수 중 큰 점수를 선택해야 한다. 하지만 값을 구하는 과정에서 행의 순서대로 쭉 탐색해서는 안되고, 1행과 2행을 번갈아가며 탐색을 해야 최적의 값을 구할 수 있다. package TT6_JUN; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public ..

평상시에 DP가 많이 약하다고 느껴서 이제 DP 문제를 위주로 풀어보려한다. DP 문제에서 중요한 점은 이전의 값을 최대한 활용해야 한다는 것이다. 굉장히 쉬운 문제이지만 DP의 감을 잡기엔 좋다고 느꼈다. package TT5_MAY; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Boj_1309 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStream..

단순히 문제만 보면 DFS구나 싶은 문제다. 하지만 맵의 크기가 500*500이고 4방향으로 탐색해야 하니 단순 DFS로 돌리면 시간초과가 난다. DFS에 DP를 추가하여 구현하면 되는데 이미 지나간 길을 다른 경로를 통해 다시 탐색하는 경우 DP처리를 해주면 된다. 입력 예시에서 동서남북 방향으로 탐색을 한다 했을때 3번째 루트를 가장 먼저 탐색한다. 그 후 2번째 루트를 탐색하게 되는데 32에서 20으로 넘어갈때 그 경로가 최적의 경로라는 것을 알고 처리하는 로직이 있으면 된다. 우선 처음 탐색할땐 전체를 다 돌아보고 마지막 지점(M,N)에 도착을 하면 1을 return 하도록 한다. 그리고 그 값을 백트래킹으로 DP배열에 저장하도록 하면 된다. 3번째 루트로 처음 탐색을 하고 나면 15, 17, 2..

우선 벽돌을 밑면의 넓이 순으로 정렬을 시킨다. 그 후 1번 벽돌부터 내 아래에 올 수 있는 벽돌이 무엇인가를 찾으며 높이를 갱신해주면 된다. 현재 선택된 벽돌보다 무거운 벽돌을 찾으면 되는데 무게가 높은 것이 여러개일 경우가 많을 것이다. 따라서 단순히 무게가 높다고 선택하는게 아닌 그 중에서도 높이가 가장 최대가 되는 것을 찾아 dp배열의 높이를 계속해서 갱신해주면 된다. 그렇게 최대 높이를 찾았다면 그 높이를 이용해 기존의 벽돌 배열을 역추적해 어떤 벽돌이 선택되었는지를 찾아주면 된다. Bricks 배열의 toString은 디버깅 때문에 썼다. package Feb_2022; import java.io.BufferedReader; import java.io.IOException; import jav..

import java.util.Scanner; public class Main2 { public static void main(String[] args) { Scanner kb = new Scanner(System.in); int n = kb.nextInt(); int[] dp = new int[n+1]; dp[1] = 0; for(int i=2;i

import java.util.Scanner; public class Main2 { public static void main(String[] args) { Scanner kb = new Scanner(System.in); int n = kb.nextInt(); int[] arr = new int[n]; int[] dp = new int[n]; int max = 0; dp[0]=1; for(int i=0;imax) max = dp[i]; } } System.out.print(max); } }

import java.util.Scanner; public class Main2 { public static void main(String[] args) { Scanner kb = new Scanner(System.in); int n = kb.nextInt(); int[] arr = new int[n]; int[] dp = new int[n]; for(int i=0;i

import java.util.Scanner; public class inf1_1 { public static void main(String[] args) { Scanner kb = new Scanner(System.in); int n = kb.nextInt(); int[][] arr = new int[n][n]; int[][] dp = new int[n][n]; for(int i=0;i