Dev.baelanche

배열의 최대길이가 20이므로 전 구간을 완전탐색한다. 처음에 좀 헤맸는데 재귀를 쓰라는 힌트를 보고 풀었다. 메모이제이션 기법만 안썼지 구현방법은 dp 와 다를게 없다. public class Main { static int n; static int s; static int a[]; static int cnt = 0; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); s = sc.nextInt(); a = new int[n]; for(int i=0; i= n) return; sum += a[idx]; if(sum == s) cnt++; recursive(idx + 1, sum - a[..

public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int card[] = new int[n]; for(int i=0; i

주어진 n*m의 배열에서 8*8 범위를 한칸씩 움직이면서 모두 검사한다. 1. BWBW... 순으로 진행하는 체스판을 90도 회전시키면 WBWB... 가 되므로 64 - 칠한 개수와 칠한 개수 중 작은 값을 최소값으로 사용한다. public static void main(String[] args){ Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = sc.nextInt(); char[][] chess = new char[m][n]; int min = 64; for(int i=0; i

문제 숫자야구 문제를 낼 수 있는 수의 범위가 123~987 사이의 865개이다. 865 * 최대 질문 횟수(100) * 각 자리수의 경우의 수(9) 를 해도 그리 크지 않으므로 이 역시 완전탐색으로 풀었다. 1. 123 부터 루프를 돌아 주어진 질문의 세자리 자연수와 비교하여 스트라이크, 볼 수가 일치할 경우만 체크한다. 2. 222, 353 등 같은 숫자가 2번 이상 올 경우는 예외처리 한다. 3. 마찬가지로 숫자 0도 예외처리 한다. public static String[] base; public static String[] s; public static String[] b; public static int cnt = 0; public static void main(String[] args) { S..

문제 자연수 범위가 1000까지 밖에 안되어서 완전탐색으로 풀었다. 1. 세 자연수의 합이 아무리커도 1000을 넘어서는 안되므로 n(n+1)/2 를 했을때 1000보다 넘지 않는 선으로 루프를 돌렸다. public static void main(String[] args){ Scanner sc = new Scanner(System.in); int t = sc.nextInt(); boolean eq = false; while(t-->0){ int x = sc.nextInt(); for(int i=1; i

문제 최대보드의 크기가 50*50 이고 한 줄 점검시 경우의 수가 50*49, 50줄을 점검해도 50*50*49 이다. 완전탐색으로 풀었다. 1. 사탕 자리를 바꿔서 최대 개수를 구한 후에는 사탕 자리를 원래대로 되돌려 놓는다. Java public class p3085 { static int n; static char c[][]; static int max; public static void main(String[] args){ Scanner sc = new Scanner(System.in); n = sc.nextInt(); c = new char[n][n]; for(int i=0;i

문제 9명 중 7명만을 고르는 경우의 수는 (8+7+6+5+4+3+2+1 >> 9*4) 36 가지이므로 완전탐색으로 풀었다. 1. 아홉난쟁이의 키를 모두 더하고 순서대로 두명의 키를 빼면서 100이 되었을 때를 찾는다. 2. 정답이 여러 가지인 경우에 아무거나 출력해도 되므로 100이 되었을 때 break 한다. Java public static void main(String[] args){ Scanner sc = new Scanner(System.in); int arr[] = new int[9]; int a=0, b=0, sum=0; for(int i=0; i

문제 자연수의 범위가 최대 1000000 이고 시간복잡도가 O(n2) 이상일 수 없으므로 완전탐색으로 접근했다. 1. 가장 작은 생성자를 구해야하니 연산할 숫자는 작은수에서 증가한다. 2. 생성자는 입력한 자연수보다 작으니 반복 범위는 n 보다 작을때이다. Java public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int i=0, sum=0; while(i= 1){ int div = se%10; se /= 10; sum += div; } if(sum == n){ System.out.println(i); break; } if(i == n) System.out.println(0); ..