https://www.acmicpc.net/problem/14391  낱개의 종이구간을 가로 또는 세로로 보는 전략을 생각 못하였다. import java.io.BufferedReader;import java.io.InputStreamReader;public class Main { static int N; static int M; static int[][] map; static int[][] sliced; static boolean[][] visited; static int ans = Integer.MIN_VALUE; static int sum; static int[] dx = {-1, 0, 1, 0}; static int[] dy = {0, 1, 0, -..

https://www.acmicpc.net/problem/1941  언뜻 보면 쉬워보였는데, 순수 dfs로 풀게되면 풀기 매우 까다롭다 1. 25C7로 25개의 좌표중에 7개를 고른 후, 2. S의 수가 4 이상인 좌표만 추린다.3. 그 좌표들을 dfs로 탐색하여 연결되어있는지 확인한다. 이정도인데, 1번은 조합을 구하는 dfs로 구하면 쉽게 구할수있고,2번도 조건문으로 쉽게 구할수있다.3번은 구현하면서 조금 해멨는데 연결만되어있는지 확인하기위해선 visited를 백트래킹할 필요없다는것을 생각하지못하였다.   import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;public class Main { ..

https://www.acmicpc.net/problem/6987   처음에 스스로 풀었을때는 통과하긴 했지만 2000ms나 걸렸다. 처음 코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.LinkedList;public class Main { static int[][] ans; static int[][] check; static boolean correct; static ArrayList list = new ArrayList(); static LinkedList set = new LinkedList(); public static..

https://www.acmicpc.net/problem/18428 import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;public class Main { static int N; static String[][] map; static boolean[][] visited; static ArrayList teacherList = new ArrayList(); static ArrayList list = new ArrayList(); static int c; static boolean ans = false; public static void main(String..

https://www.acmicpc.net/problem/2661    문제를 보고나서, backtracking을 이용한 순열을 만들고, 순열을 하나 증가시킬때마다 이게 좋은수열인지 나쁜 수열인지 확인하는 과정으로 풀수 있겠구나 생각했다. 그런데 문제는, TLE가 뜨냐 안뜨냐였는데, 문제조건에서 N은 최대 80이라고 했고, 숫자는 [1,2,3]만 허용한다했으니최악의경우 3^80번 순열을 만들어야 하므로 당연히 시간초과가 날 것이라고 생각했다. 그래서 이건 백트래킹으로 풀수 없는 문제인가 싶어서 다른 방법을 생각해보았지만 도저히 떠오르지않았고,순열을 만드는 숫자 후보 [1,2,3]을 작은 수부터 그리디하게 고르면 혹시 통과를 할수 있지 않을까? 생각해서 구현을 해보았는데 신기하게도 시간이 매우 적게 걸렸다..

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..

치킨집이 최대 13개고, 각 집에대한 치킨거리는 O(1)로 구할수있기때문에 브루트포스로 한다고 했을떄 13Cn * 2N이 최대이다.이경우 시간이 넉넉하기떄문에브루트포스로 일일히 치킨집을 조합해서 다 경우의수를 따져봐도 시간초과가 나지않는다. 그러나 아이디어는 다 생각했는데 치킨집 조합을 어떻게 브루트포스로 조합하지?멍청하게 이걸 몰라서 문제를 못풀어 답을 봤다. dfs + 백트래킹으로 조합을 따질 수 있었다.이런 풀이는 많이 나오니까 어느정도 구조를 외우고 나중에 또 비슷한 문제풀이가나올때 바로 떠올릴수있도록 반복해야겠다고 생각했다.  import javax.sound.sampled.Line;import java.awt.*;import java.io.BufferedReader;import java.io...

https://www.acmicpc.net/problem/1759 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.HashSet; public class Main { public static int L; public static int C; public static char[] words; public static char[] pwd; public static boolean[] visited; public s..