Dev.baelanche

주어진 수 n이 3의 배수이면 나누기 3, 2의 배수이면 나누기 2, 그 외 일때는 1을 뺀다. 한번 연산을 수행했을때마다 /3, /2, -1 중에서 가장 1이 빨리 될 경우를 찾아서 연산한다. 제한시간이 2초이므로 메모이제이션 기법을 사용하였다. 1. 동적배열을 만들어 나올 수 없는 수로 초기화 한 후, 각 수 마다 최선의 횟수를 배열에 담는다. 2. n 이 1일때는 예외처리한다. 3. n 이 1일때 0 을 리턴하는 것으로 처리하였으므로 나머지 경우엔 연산을 +1 한다. public static ArrayList dp = new ArrayList(); public static int makeOne(int n) { if(n == 1) return 0; if(dp.get(n) != -1) return dp..

문제 숫자야구 문제를 낼 수 있는 수의 범위가 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); ..