1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 import java.util.*; import java.io.*; public class Main { static boolean[]visit; static ArrayList []ad; static int result[]; static int nV; //노드의 개수 static int nE; //간선 public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 import java.lang.reflect.Array; import java.util.*; import java.io.*; public class Main { static ArrayList [] ad; static boolean[] visit; static int nV, nE; static int component = 0; public static void main(String[] args) throws IOExceptio..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 import java.lang.reflect.Array; import java.util.*; import java.io.*; public class Main { static ArrayList [] ad; static boolean[] visit = new boolean[101]; static int nV, nE; static int n, m; static int result = -1; public static void main(S..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 import java.util.*; import java.io.*; public class Main { static int[][] ad = new int[5][5]; static Set set = new HashSet(); public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; for(int i = 0; i

이 문제는 할 때마다 시간 초과가 나올 수도 있고, 맞았습니다라고 뜬다. 이 경우는 시간 복잡도가 코드 제한시간에 걸쳐서 제출했을 때, 되는 경우도 있고, 안 되는 경우도 있다고들 한다. 비록 많은 문제를 풀진 않았지만 이런 경우도 있다고들 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 import java.io.*; import java.util.*; public class Main { sta..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int nV; //정점 수 static int nE; //간선 수 static int[][] arr; static boolean[] visit; static int cnt = -1; public static void ..

이 문제를 처음에 접할 때, 문제가 무슨 말인지 이해가 가질 않았다. 그래서 힌트를 보고 문제가 무슨 말을 하고 싶었는지 알 수 있었다. 그러고 나서 점화식을 어떻게 찾을지 N = 1부터 N = 3까지 개수를 다 써보았다. 하지만 처음에는 이차원 배열을 생각하지 못하고, 규칙만 찾았는데 표로 정리해보니 이차원 배열을 사용하면 되겠다는 생각이 들었다. 그래서 기본 점화식인 dp[i][j] = dp[i-1][j] + dp[i][j-1]을 구했었다. 하지만 if( j == 0) 이 부분을 생각하지 못하고 N = 1일 때만 1로 초기화를 시키고 나머지 dp [N][k]에서 k가 0일 때, 1로 어떻게 초기화를 시켜야 하나 엄청 고민을 했다. 그래서 고민을 풀지 못한 채 점화식만 찾고 풀이를 하질 못했다. 그래서..

Top down 방식 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static int[] dp; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStrea..

이 문제를 처음에 접할 때, 이차원 배열, 일차원 배열을 생각하면서 접근했다. 그런데 n = 1부터 n = 5까지 그림을 그리면서 하는데 규칙성이 보이게 됬다. 피보나치와 비슷한 규칙을 가지게 된다. Top down 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static int[] dp; public ..

이 문제는 dp의 가장 기본적인 문제라고 한다. 처음에 이 문제를 보았을 때에는 cnt 변수를 선언해서 연산을 할 때마다 더해준다라는 생각으로 접근을 했다. 하지만 cnt값을 계속 증가해주기 때문에 연산의 최소가 비교가 되질 않았다. 그래서 풀지 못하고 힌트를 보았다. 그래서 보니 cnt을 설정하지 않고 -1 연산할 때, /2 연산할 때, /3 연산할 때 +1을 해주는 것이다. 왜냐하면 연산을 해주었기 때문이다. 그래서 dp[n] 에는 n이 1이 될때까지의 연산 횟수를 저장하는 것이다. 예로 10을 들어보자. 그러면 10을 1 뺄수 있고, 2로 나눌 수도 있다. 그러면 9 와 5가 된다. 여기서 9를 3 으로 나누고 또 3으로 나눌 수 있다. 총 연산 수는 3이다. 5를 -1 하고 4를 2로 2번 나누면..