IT 개발 돼지의 일상

출저 : https://www.acmicpc.net/problem/14500 "DFS 로 4칸을 간다. ㅗ 경우는 별도로 처리" DFS를 통해 4칸을 이동하면 테트로미노의 도형 4가지를 구할 수 있다. 문제는 의 처리이다. 아래와 같이 처리해 주었다. map을 다시 for 문을 돌면서 4개 셀의 값을 선택하여 처리한다. 1 : ㅗ 만들 수 없는 경우2 : 그냥 선택한 4개 셀을 다 더하면 되는 경우3 : 중앙값 + ( 4개 셀의 값 - 이중 최소인 값) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757..

출저 : https://www.acmicpc.net/problem/14501 "시뮬레이션" 12345678910111213141516171819202122232425262728293031323334353637import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { static int N; static int map[][]; static int max = 0; public static void main(String[] args) throws IOException { BufferedReader br = new ..

출저 : https://www.acmicpc.net/problem/2309 "DFS" 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051import java.util.Arrays;import java.util.Scanner; public class Main { static int[] talls = new int[9]; static boolean[] visited = new boolean[9]; static boolean find; static int[] res = new int[7]; static Scanner sc = new Scanner(System.in); public static v..

출저 : https://www.acmicpc.net/problem/9205 "가지치기, 플로이드워셜" 풀다가 시간초과가 났다. 가지치기나 DP 등이 필요할거 같다는 생각이 들었고, 갈수 있냐 없냐의 문제였음. 그냥 특정 지점에 맥주를 가장 많이 들고 간 경우만 지나갈 수 있게 해줬다... 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java..

출저 : https://www.acmicpc.net/problem/1592 "시뮬레이션" 1234567891011121314151617181920212223242526272829303132333435import java.util.Scanner; public class Main { static int n,m,l; static int[] map; static int cur, next; static int res; static Scanner sc = new Scanner(System.in); public static void main(String[] args) { n = sc.nextInt(); m = sc.nextInt(); l = sc.nextInt(); map = new int[n]; while(true..

출저 : https://www.acmicpc.net/problem/14889 "비트마스크도 쓸수 있고, 그냥 DFS 로 짝지어서 할 수도 있고" 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer; class Main { static int N; static int[][] map; static bo..

출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc "가장 많이 열리는 걸 열고, 그다음에 차근차근." 알고리즘 기본 로직은 맵에서 주위에 지뢰가 없는 칸을 탐색해 먼저 클릭하여 해당 칸을 오픈한다. 이렇게 오픈된 나머지 8칸에 대해서도 똑같은 검사를 한다. 이렇게 하여 주위에 지뢰가 없는 칸들이 모두 없어 지게 되고, 그 후에 남아있는 칸들의 수를 세서 최종 값을 더한다. 이때, 지뢰가 없는 칸의 탐색은 BFS를 통해 한다. 더해서 아래 큐에 들어가는 중에 중복이 생겨났었고, 시간초과가 났다. 탐색은 중복을 줄이는 것이 정말 중요하다. visited 배열을 두어 다시 들어가지 않..

출저 : https://www.acmicpc.net/problem/1783 "그리디 알고리즘, 내 머리속으로 계산." 여러 조건들이 있었다. 오른쪽으로만 이동하며, 이동 횟수가 4가 넘어가는 경우 가능한 4가지의 방법 모두 적어도 한번씩은 사용해야 한다. 이러한 부분들을 조건문으로 분기시킨다... 잘 생각해보자. n이 1,2,3,... 일때를 생각해보고, m이 7보다 작을때, 크거나 같을 때를 생각해보자. 12345678910111213141516171819202122232425import java.util.Scanner; public class Main { static int n,m; static Scanner sc = new Scanner(System.in); public static void mai..

출저 : https://www.acmicpc.net/problem/3055 "순서를 잘 생각한 BFS 두개." 먼저 물과 고슴도치를 이동 시키기 위해 두개의 Queue를 준비한다. 두개의 queue는 각 time 마다. 상하좌우로 이동할 것이다. 이때 물과 고슴도치 중 어떤 것을 먼저 움직여야 할까? 문제에 조건에 따르면 다음 시간에 물이 찰 곳에는 고슴도치가 이동하지 못한다고 했으므로, 물을 먼저 이동 시켜주고, 물이 찰 곳에 고슴도치가 이동하지 못하도록 해주어야 한다. (만약 고슴도치가 수영을 N 번 할 수 있다고 한다면 문제가 어려워 질거같다... ) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546..

출저 : https://www.acmicpc.net/problem/1937 "DP" DP를 이용한 문제이다. top down 방식을 사용한다. 재귀를 할 때, 리턴 값이 있는 경우 처리를 잘해 주어야 겠다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer; public class Main { s..