전공공부

설명 이전의 상태 값을 기억하고 최소한의 값으로 지속적인 탐색을 통해서 값을 구했습니다. O(N)이 걸렸고 정답 값이 오버플로우가 나기 때문에 long으로 설정하는 것이 중요했습니다. 코드 package BOJ.greedy; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ_13305 { public static void main(String[] args) throws Exception{ BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer t..

설명 코드를 간결하게 짜려고 노력했습니다. 사실 실버 4 문제라서 크게 설명이 필요 없을 듯하고 해서 최대한 간결한 형태로 짜봤습니다. 코드 package BOJ.greedy; import java.util.*; public class BOJ_1758 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); List arr = new ArrayList(); for (int i = 0; i < N; i++){ arr.add(sc.nextLong()); } arr.sort(Comparator.reverseOrder()); long ans = 0; for (int i = 0; i < a..

설명 그리디하게 풀면 되는 문제입니다. 결국 X가 4의 배수만큼 이거나 4의 나눗셈 값이 나오는 만큼 AAAA를 붙이고 짝수개의 나머지 X가 나오면 BB 또는 4의 배수이면 AAAA로 채워버리면 됩니다. 따라서, 문제의 주어진 X의 값을 가져와서 읽고 이를 선택해서 사용하면 됩니다. 만일, X가 3개라면 홀수 개라서 AAAA,BB로는 채울 수 없죠. 코드 package BOJ.greedy; import java.io.*; public class BOJ_1343 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); St..

설명 코인의 가치를 인덱스의 위치로 잡고 이에 따라서 인덱스의 위치 값에 따른 경우의 수를 구했습니다. dp[i] += dp[i - 동전의 가치] 코드 package BOJ.Dynamic_Programming; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ_2293 { static int N,K; static int[] coins; static long[] dp; private static void input() throws IOException { BufferedReader in = new Bu..

설명 DP를 활용한 문제이고 이때, 들어오는 도시마다 최소한 투자를 통해서 내가 만들어야하는 고객치를 딱 도달하는 것이 포인트 였습니다. 따라서, DP의 인덱스를 내가 최소한의 투자를 통해서 만들 수 있는 고객 유치 한계점으로 잡고 문제에 따른 조건을 만들었습니다. 나름 깔끔하게 메서드 별 역할을 나눠서 행동하게끔 구성을 해보았는데 생각보다는 별로네요. 좀 더 효율적으로 나누는 방법을 고려하는 것도 좋을 것 같습니다. 코드 package BOJ.Dynamic_Programming; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;..

설명 어떻게 보면 메모리제이션을 활용한 문제입니다. 이전의 상태 값을 가지고 다음에 진행 할 때 그 상태값을 가진 수에 대해서만 진행을 시켰으니깐요. (처음 dp를 초기화 하고 나머지를 빼는 이유) 그리고, 각 dp는 각 점프의 횟수를 나타냅니다. 코드 package BOJ.Dynamic_Programming; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ_11060 { public static void main(String[] args) throws Exception{ BufferedReader in = new BufferedReader(new..

설명 저는 DP 형태의 메모리제이션을 활용하여서 문제를 풀었습니다. 보시다 싶이 문제 조건만 맞추면 풀 수 있는 문제라서 따로 풀이가 필요하지는 않을 듯하고 메모리제이션을 적절히 사용하는 것이 포인트 일 것 같습니다. 코드 package BOJ.Dynamic_Programming; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ_22869 { public static void main(String[] args) throws Exception{ BufferedReader in = new BufferedReader(new InputStreamReade..

설명 점화식의 구현은 쉬운 문제이나 예외 케이스를 산정하는 것이 힘들었습니다. 이전의 값을 기억하고 다음 값에 상자 상태 값을 넘겨줘서 푸는 형식으로 구현을 하였습니다. 코드 package BOJ.Dynamic_Programming; import java.util.Scanner; public class BOJ_1965 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] arr = new int[N]; for (int i = 0; i < N; i++){ arr[i] = sc.nextInt(); } int[] dp = new int[N]; int ans = 0; for..