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/1446   점화식을 세울 수 있다.dp는 나름대로 노하우가 생겼는데1) dp배열이 의미하는것이 무엇인지를 명확히 세우는것이 중요하고,2) 항상 i 와 i + 1의 관계를 생각하면 잘 떠오르는것같다. 최대한 다른것들은 배제하고, 컴팩트하게 i 와 i + 1의 관계만을 생각하면 된다.  제일 중요한것은 dp[i]가 무엇인지 정의를 해야한다, dp[i]란 i까지 도착하는데 걸리는 최솟길이 라고 정의했다. 그다음 점화식을 세워야 한다. 최대한 i 와 i + 1 관계 외에 다른 복잡한 생각을 지웠더니 은근히 잘 떠오를 수 있었다.점화식1) (도착점이 i인 지름길이 존재할 때) ->  dp[i] = min(dp[i] , dp[지름길의 시작점] + 지름길의 ..

https://www.acmicpc.net/problem/7795  Test case의 범위가 주어지지않아서 bruteForce로 해도 되나 싶어서 해보았더니 시간초과가 났다.(정렬후 그리디하게 bruteforce로 접근하면 통과는 된다고 한다) 이분탐색을 사용하기위해, B를 정렬한뒤, A에서 순차적으로 element를 하나 씩 꺼내어 정렬된 B에 이분탐색을 한 후 lower bound index를 구해주면 된다.  lower bound로 구하는이유는 B에 같은 element가 여러개 올 수 있기 때문이다. import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;public class Main { s..

https://www.acmicpc.net/problem/2477 특정 알고리즘을쓰는것이 아닌 구현문제에서는 답을 구하는데에 있어서 패턴을 찾는것이 중요하다. 1. 반시계방향으로 돌아야 정상인데 갑자기 시계방향으로 도는 부분이 생긴다 -> 그곳이 빈공간이기 때문에 빈공간 계산2.만약 다돌았는데 시계방향으로 도는 부분이 없다 -> 내가 우연히 맨 처음 시작점을 시계방향으로 도는 부분으로 정했다.  이렇게 케이스를 두개로 나누었다.  import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;public class Main { static int count; static ArrayList list..

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/board/view/108208  문제 유형은 브루트포스였으나, 이중for문을돌면 5억번을 도므로, 시간초과가 나기때문에최대한 가지치기를하거나, 중복되는 케이스를 피해야하는데도저히 떠오르지 않아서 검색을 해보니 에라토스 테네스의 체를 응용하는 문제였다고 한다.   import java.io.BufferedReader;import java.io.InputStreamReader;public class Main { static int[] arr = new int[1000001]; static int[] num ; static int[] ans; static int N; public static void main(String[] args) t..

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