하다보면 늘겠지

📍 문제 설명 💡 접근 최대 부분 증가 수열을 출력하는 문제 출력할 때 dp 테이블을 참조하여 최대 길이부터 1씩 작아지면서 스택에 넣고 출력하면 된다. 👩‍💻 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { static int n, m, answer; static int[][] board; static int[] arr, dp; static boolean[][] visited; static int[] dx = {-1,1,0,0}; static int[] dy = {0,0,-1,1}; static ArrayList list = new ArrayList(); st..

📍 문제 설명 💡 접근 인프런 강의에서 배웠던 최대부분증가수열(LIS) 문제다. dp[n]을 n번째 인덱스를 마지막 항으로 하는 최대 증가 부분 수열로 둔다. i = 1일 때 j = 0 탐색 j = 0 -> arr[0] max 이므로 max = dp[0] = 1 dp[1] = 1 + 1 = 2 i = 2일 때 j = 1, 0 탐색 j = 1 -> 이전 항이 더 크다. dp[2] = 1 j = 0 -> 이전 항이랑 같다. dp[2] = 1 i = 3일 때 j = 2, 1, 0 탐색 j = 2 ->max = 1 dp[3] = 2 j = 1 ->max = 2 dp[3] = 3 j = 0 -> dp[0] < max dp[3] = 3 👩‍💻 코드 import java.io.Bu..

📍 문제 설명 💡 접근 1자리일 때 1 -- 1 2자리일 때 1 -- 10 3자리일 때 2 -- 100 101 4자리일 때 3 -- 1000 1001 1010 5자리일 때 5 -- 10000 10001 10010 10100 10101 피나보치 문제다. 👩‍💻 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { static int n, m, answer; static int[][] board; static long[] arr, dp; static boolean[][] visited; static int[] dx = {-1,1,0,0}; static int[] dy =..

📍 문제 설명 💡 접근 0, 9를 제외한 숫자를 제외하고는 2개를 더해줄 수 있다. 👩‍💻 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static long mod = 1000000000; static int n, m, answer; static int[][] board; static long[][] arr, dp; static boolean[][] visited; static int[] dx = {-1,1,0,0}; static int[] dy = {0,0,-1,1}; static ArrayList list..

📍 문제 설명 💡 접근 최대 금액을 담을 배열 dp[n]이 필요하다. 점화식을 세워야하는데. dp[4] 부터 보자면 1장 + 3장 가격 2장 + 2장 가격 3장 + 1장 가격 4장 + 0장 가격의 최댓값을 뽑아내면 된다. 따라서 점화식은 dp[i] = Math.max(dp[i], dp[i-j] + dp[j]); 로 사용할 수 있다. 타 블로그를 참고해보니 dp[j]가 아닌 arr[j]의 값을 넣었는데 금액 n까지의 최대 금액 구하는 문제라서 둘이 비슷한 의미로 사용할 수 있겠다. 👩‍💻 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public ..

📍 문제 설명 💡 접근 N의 범위가 커서 브루트포스로는 시간초과 나는 문제 n이라는 숫자가 m으로 끝나는 방법의 수를 담을 2차원 배열을 사용해야한다. dp[1][1] = 1 (1) dp[2][2] = 1 (2) dp[3][1] = 1 (2+1) dp[3][2] = 1 (1+2) dp[3][3] = 1 (3) dp[4][1] = 2 (3+1, 1+2+1) dp[4][3] = 1 (1+3) dp[n][1]의 일 때 dp[n-1][1]은 연속된 숫자가 되므로 제외하고 dp[n-1][2],dp[n-1][3] 에서 구한 방법의 수를 더해준다. dp[n][2]의 일 때 dp[n-2][2]은 연속된 숫자가 되므로 제외하고 dp[n-2][1],dp[n-2][3] 에서 구한 방법의 수를 더해준다. dp[n][3]의 일..

📍 문제 설명 💡 접근 바닥공사 문제와 같은 문제 👩‍💻 코드 import java.util.*; public class Main { static int n, m, answer; static int[][] board; static int[] dp; static boolean[][] visited; static int[] dx = {-1,1,0,0}; static int[] dy = {0,0,-1,1}; static ArrayList list = new ArrayList(); static StringBuilder sb = new StringBuilder(); public static void main(String[] args) { Scanner kb = new Scanner(System.in); Main ..

📍 문제 설명 💡 접근 스도쿠 문제와 접근 방식은 비슷하다. 1.현재 위치의 값을 가로 숫자로 사용할 것인지 세로 숫자로 사용할 것인지 visited 배열로 판단한다. 2.모든 열을 탐색했으면 다음 행의 0열부터 다시 탐색한다. 3.모든 행을 탐색했으면 visited 배열에 맞게 가로의 합 + 세로의 합을 구한다. 👩‍💻 코드 import java.util.*; public class Main { static int n, m, answer; static int[][] board; static boolean[][] visited; static int[] dx = {-1,1,0,0}; static int[] dy = {0,0,-1,1}; static ArrayList list = new ArrayList()..

📍 문제 설명 💡 접근 부분수열의 합으로 사용한다/사용하지않는다. 로 풀 수 있는 문제 단, 모두 사용하지 않는 경우에는 합이 0이므로 s가 0일땐 하나 빼줘야한다. 👩‍💻 코드 import java.util.*; public class Main { static int n, m, s, answer; static int[][] board; static char[] c; static int[] arr,pm; static boolean[] visited; static int[] dx = {-1,1,0,0}; static int[] dy = {0,0,-1,1}; static ArrayList list = new ArrayList(); static StringBuilder sb = new StringBuilder..

📍 문제 설명 💡 접근 전형적인 조합문제다. k개 중에 6개 뽑는 것을 k = 0을 만날때까지 반복한다. 👩‍💻 코드 import java.util.*; public class Main { static int n, m, k, sum, answer = Integer.MAX_VALUE; static int[][] board; static char[] c; static int[] arr,pm; static boolean[] visited; static int[] dx = {-1,1,0,0}; static int[] dy = {0,0,-1,1}; static ArrayList list = new ArrayList(); static StringBuilder sb = new StringBuilder(); publi..