https://www.acmicpc.net/problem/2023  백트래킹을 이용한 브루트포스문제이며흔히나오는 유형중 순열문제라고 할수있다소수가 절대 될수없는수 (4,6,8)를 제외한 (1,2,3,5,7,9)의 모든 순열을 나열하여 , 그 각각을 소수체크해주면 풀릴 수 있는 문제였다 import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;public class Main { public static TreeSet set = new TreeSet(); public static ArrayList list = new ArrayList(); public static int N; public stati..

import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int[][] dp; // 마지막 상자가 i번째인 가장 큰 가치 . int[] weight; int[] value; for (int k = 1; k = weight[i]) { //i번째 인덱스를 넣을수 있다면 ..

dfs + 백트래킹을 구현만 하면 정답인 문제였고HashSet의 add(), remove(), contains()가 O(1)인것을 이용해 HashSet을 통해 풀었다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashSet; public class Main { public static int max = Integer.MIN_VALUE; public static int R ; public static int C ; public static String[][] map; public static HashSet set = n..

https://www.acmicpc.net/problem/2096   맨 처음 풀었을떄 코드 :  bfs -> 메모리초과import org.w3c.dom.Node;import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;public class Main { public static int N; public static int[][] map; public static int max = Integer.MIN_VALUE; public static int min = Integer.MAX_VALUE; public static Queue queue = new LinkedList(); public ..

https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모www.acmicpc.net   문제를 보고 .replace()같은 라이브러리를 쓰면 무조건 시간초과가 날것이 뻔했으므로O(N)혹은 최대 O(KN) (K = 36)안에 문제를 해결하는 방법을 찾다가문자열 수식에서 괄호의 유효성을 체크하는 문제가 떠올라서스택으로 풀었다. 처음에 한번 풀다가 틀렸었는데 틀린 이유는 모든 문자를 일단 스택에 집어넣어야한다는점을 간과했다. 나는 PS를 할때 자바를 사용하는데 그 이유는 클..

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연www.acmicpc.net   단순히 모든 node에대해 dfs / bfs를 수행해도 통과할수있는 문제  1) - 단순 bfs + 브루트포스import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;public class Main { public static int N; public static int ans;..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그www.acmicpc.netimport java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;public class Main { public static int N; public static int V; public static ArrayList[] adjacentList; public stat..

https://www.acmicpc.net/problem/1753 1753번: 최단경로첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가www.acmicpc.net   방문노드체크 + 우선순위 큐 + 다익스트라 로 최대한 그리디하게 풀지않으면 메모리초과가 난다. import java.io.BufferedReader;import java.io.InputStreamReader;import java.lang.reflect.Array;import java.util.*;public class Main { public static..