DFS / BFS 모두 사용 가능한 문제다. 시간이 넉넉한 문제라면 DFS로 푸는 게 코드가 짧아져서 DFS로 풀었다. 다른 DFS 문제와는 다르게 노드들이 이어져 있지 않을 수 있어서 조금 시간이 걸렸다. 최종 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int n, m; static int arr[][]; static boolean visit[]; static int answer; public static void main(String[] args) throws Exception { BufferedReader br =..

문제 설명에 C++ 코드가 있길래 C++ 전용 문제인 줄 알고 안 풀었었다. 근데 해결한 사람들이 많은 문제여서 다시 보니 그냥 피보나치 함수 변형이었다. F(0)과 F(1) 호출을 횟수를 세면 되는 문제이다. 처음에 아무 생각 없이 똑같이 재귀로 구현하고 시간 초과로 틀렸다. 연습장에 F(2), F(3) ... 호출 횟수를 몇 번 써보니 결국 DP라는 것을 알게 돼서 해결했다. 2차원 배열로 0이 호출된 횟수와 1이 호출된 횟수를 저장했다. 최종 코드 import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { static int t; static int[][] dp; static StringBuilder sb ..

다각형의 면적을 구하는 신발끈 공식을 알면 바로 풀 수 있는 문제이다. 다만 오버플로우를 생각하지 않아 몇 번을 틀렸다... 입력값을 보면서 오버플로우가 생길수 있는지 먼저 생각해야겠다 최종 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int n; static long[] x, y; static double resultX, resultY ,resultSum; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedRe..

괄호를 어디에 치느냐에 따라 값이 달라지기 때문에 최솟값을 얻으려면 -를 기준으로 문자열을 나눠 모두 더한뒤 마지막에 -연산을 수행하면 된다. 설계는 어렵지 않았는데 문자열을 분리하는게 쉽지 않았다. Stringtokenizer를 이용하여 문제를 풀었다. 최종 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in))..

2xn 타일링 1 보다 약간 더 어려워진 문제이다. 점화식을 찾는데 시간이 좀 걸렸지만 찾으면 2xn 타일링 1과 똑같이 풀 수 있다. 최종 코드 import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); System.out.println(bottomUp(n)); } static int bottomUp(int ..

문제를 보고 전형적인 DP 문제라고 생각했다. 점화식은 DP[n] = DP[n-1] + DP[n-2]로 조금만 생각해보면 금방 나오는 간단한 문제다. 이 문제를 풀면서 느꼈던것은 입력값이 최소인 1인 경우 평소 하던것처럼 배열을 n+1만 생성하면 dp[2]가 들어갈 공간이 없어서 ArrayIndexOutOfBounds가 난다는것과 메서드를 리턴 받고 나중에 10007로 나눈다면 입력값이 1000일 때 바로 오버플로우 문제가 일어나기 때문에 dp배열에 값을 저장할 때마다 10007로 나눠서 저장해야 한다는 점이다. 두 가지를 생각하지 못해 제출을 8번이나 했다. 최종 코드 import java.io.BufferedReader; import java.io.InputStreamReader; public cla..

PrioritiyQueue를 이용하면 간단하게 풀 수 있는 문제였다. 나는 If - eles 문으로 처리했지만 0을 고려해서 순서로 정렬해야 한다면 Compare 메서드를 오버라이딩 하면 될 것 같다. PrioritiyQueue를 사용하지 않고 Heap을 직접 구현하는 분들도 계시던데 나중에 한번 시도해봐야겠다. 최종 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.PriorityQueue; public class Main { public static void main(String[] ..

Map에 입력값을 넣고 key에 맞는 value 값만 출력하면 되는 문제다. 입출력 값이 길어지면 시간 초과가 날수도 있겠다는 생각을 해서 BufferedWriter를 사용했다. 아주 간단하고 쉬운 문제였다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.HashMap; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws Exception{ BufferedReade..

1012 - 유기농 배추와 비슷한 문제였다. DFS를 이용해서 풀었는데 결과가 계속 틀렸다고 나왔다. 맞왜틀을 30분이나 하고서는 문제에서 출력을 오름차순으로 하라는 것을 발견했다... 정렬되게 수정하고 다시 제출해도 또 틀렸다고 나오길래 1시간을 고민했다. 문제는 visit 배열을 사용하지 않아서 하나의 단지에서 하나의 아파트만 있다면 0으로 리턴되는 것이 문제였다. visit 배열을 안 쓰고 답을 내고 싶어서 고민하다가 탐색한 집은 0으로 바꾸고 좌표를 이동시키고 재귀호출을 하면 정답이 되는 것을 발견했다. 다음부터는 그냥 visit 배열을 사용해서 풀어야겠다... 최종 코드 import java.io.BufferedReader; import java.io.IOException; import java..