하다보면 늘겠지

📍 문제 설명 💡 접근 A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다. 라는 조건을 확인해보면 총 인원이 얼마든 5명의 사람이 각각 순서대로 친구 관계라면 정답인 문제다. 따라서 모든 지점에 대해서 각각 탐색을 해야 한다. 1.탐색 지점을 방문 처리하고 갈 수 있는 정점 중에서 방문하지 않은 정점을 갈 수 있는 만큼 가본다. 2.친구관계를 올바르게 찾지 못했을 경우(갈 수 있는 경로가 더 이상 없는 경우) 타 지점으로도 찾아볼 수 있도록 갔던 곳의 방문 체크를 풀어준다. 3.친구관계 찾았으면 더 볼 필요 없이 바로 끝내버린다. 👩‍💻 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java..

📍 문제 설명 💡 접근 수를 제거하지 않는 최대합과 수를 한 번 제거하는 최대합을 표현하는 2차월 배열을 이용한다. 1. 수를 제거하지 않는 경우 이 경우에는 기존 연속합 문제와 동일하다. 2. 수를 제거하는 경우 이 경우에는 수를 제거 한 적이 있는지/없는지 판단하여 최댓값을 구한다. 수를 제거 한 적이 있으면 현재 인덱스의 숫자를 지우지 못하므로 dp[i-1][1] + arr[i] 수를 제거 한 적이 없으면 현재 인덱스의 숫자를 지울 수 있으므로 dp[i-1][0] 이 중의 최댓값이 dp[i][1]에 들어간다. 👩‍💻 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Ma..

📍 문제 설명 💡 접근 가장 긴 증가하는 부분 수열 + 가장 긴 감소하는 부분 수열을 합친 문제이다. 2개로 나뉜 배열에 최대 수열 길이 각각 넣는다. 예를 들면 inc_dp[1] = {1,5} = 2 dec_dp[1] = {5,4,3,2,1} = 5 가 된다 이 두개를 합치면 {1,5 5,4,3,2,1}이 되고 중복되는 5를 제거 하여 {1,5,4,3,2,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, inc_dp, dec..

📍 문제 설명 💡 접근 LIS 문제와 거의 동일한 문제 범위에 맞지 않거나(i = 0) 현재의 값이 이전 항들보다 제일 클 수 있으므로 초기화할 때 dp에 arr의 값들을 넣어준다. 2가지 조건을 만족하면 값을 바꿀 수 있다. 1. 이전 항의 숫자가 현재 항의 숫자보다 작아야 더할 수 있다. 2. 이전 항의 합 + 현재 항의 값이 현재 항의 합보다 커야한다. 👩‍💻 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { static int n, m, answer, min, max; static int[][] board; static int[] arr, dp; stati..

📍 문제 설명 💡 접근 n번 까지 포도주를 먹는 방법 중 최대로 마실 수 있는 배열을 사용한다. 3가지의 경우의 수가 있다. 1. 현재 포도주를 먹지 않았을 때는 바로 직전까지의 포도주를 먹을 수 있다. 2. 현재 포도주를 먹었을 때는 직전의 직전까지의 포도주를 먹을 수 있다. 3. 또 다른 경우로는 현재 포도주를 먹고 바로 직전의 포도주를 먹을 수도 있다. 그 중 최댓값을 넣는다. 👩‍💻 코드 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 = Int..

📍 문제 설명 💡 접근 쉬운 계단수 문제와 비슷한 문제 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..