하다보면 늘겠지

📍 문제 설명 💡 접근 쉬운 계단수 문제와 비슷한 문제 i 자리의 숫자가 j라는 숫자로 끝나는 경우의 수를 표현하는 2차원 dp 배열을 사용한다. dp[2][0] = 1 dp[2][1] = 2 ... dp[2][9] = 10 👩‍💻 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static int n, m, k, min, max, answer = Integer.MAX_VALUE, mod = 10007; static int[][] board; static int[][] arr, dp, t, p; static bo..

📍 문제 설명 💡 접근 2차원 배열을 이용한다. 위쪽 우리의 사자의 위치에 따라 경우의 수를 계산한다. 사자가 없거나 왼쪽에 사자가 있거나 오른쪽에 사자가 있거나 3가지 중에 하나이다. 사자가 없으면 어느 위치에도 구애 받지 않으므로 놓지 않거나/왼쪽에 놓거나/오른쪽에 놓거나가 된다. 사자가 왼쪽에 있으면 놓지 않거나/오른쪽에 놓거나가 된다. 사자가 오른쪽에 있으면 놓지 않거나/왼쪽에 놓거나가 된다. 👩‍💻 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static int n, m, answer = Intege..

📍 문제 설명 💡 접근 첫번째에 작은 값을 선택했을 때 최종 값이 최솟값이 되는지 보장할 수 없으므로 그리디 방식으로는 못푼다. 2차원 배열을 이용하여 n번째 항에 각 색깔을 칠했을 때의 최소 비용을 각각 넣는다. 마지막에 들어가 있는 값들 중 최솟값이 모든 집을 칠하는 비용의 최솟값이다. 👩‍💻 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static int n, m, answer = Integer.MAX_VALUE, max, k, min; static int[][] board; static int[][] ..

📍 문제 설명 💡 접근 dp[n]을 n까지의 제곱 수 합의 최소 갯수라고 정의해놓는다. 1 ~ n까지 탐색하는데 현재의 숫자에서 제곱수가 구해지는 부분이 있으면 구한다. 13을 예로 들면 제곱수가 1 2 3이 나올텐데 마지막 항이 1의 제곱수일 땐 d[12] + 1(= 13)의 값을 1제곱 13개 마지막 항이 2의 제곱수일 땐 d[9] + 1(= 2)의 값을 (3제곱+2제곱) 마지막 항이 3의 제곱수일 땐 d[4] + 1(= 2)의 값을 (2제곱+3제곱) 구하게 된다. 👩‍💻 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { static int n, m, answ..

📍 문제 설명 💡 접근 dp[n]을 n번 인덱스를 마지막 항으로 하는 최대합으로 한다. 이전 항의 최대합 + 현재항, 현재항 중에서 큰 값을 넣는다. 👩‍💻 코드 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(); stat..

📍 문제 설명 💡 접근 최대 부분 증가 수열을 출력하는 문제 출력할 때 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 ..