반응형
백트래킹 ..,,,
N(최대 100) 장중에 3장을 뽑아서 M보다 작은 최대값을 찾아라.!
100C3 이므로 시간초과가 나지 않는다. 메모리 초과도 나지 않는다.
백트래킹으로 100C3의 모든 경우를 계산해주면 된다.
풀이
1. 백트래킹으로 부분집합 (모든 경우의 수) 를 계산한다.
2. 3개만 선택하면 되므로 depth는 2일때이다. (0부터 시작했으니깐)
3. M보다 크지않은 최대값을 고르면 끄읏.
소스
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.io.BufferedReader; import java.io.InputStreamReader; class Main { static BufferedReader br; static int N; static int M; static int max; static int result; static int[] arr; static boolean[] visited; static String[] str; public static void main(String[] args) throws Exception { br = new BufferedReader(new InputStreamReader(System.in)); str = br.readLine().split(" "); N = Integer.parseInt(str[0]); M = Integer.parseInt(str[1]); max = Integer.MAX_VALUE; arr = new int[N]; visited = new boolean[N]; str = br.readLine().split(" "); for (int i = 0; i < N; i++) { arr[i] = Integer.parseInt(str[i]); } //-----------------입력부----------------- for (int i = 0; i < N; i++) { visited[i] = true; DFS(i, 0, arr[i]); visited[i] = false; } System.out.println(result); } public static void DFS(int start, int depth, int sum) { //depth가 0부터 시작 했으므로 depth==2이면 3개의 카드를 골랐을 경우이다. if (depth == 2) { //M보다 크지않은 최대값을 고른다. if (Math.abs(M - sum) < max && sum <= M) { max = Math.abs(M - sum); result = sum; } return; } //3개를 고르는 알고리즘.visited[] 함수를 통해 백트래킹으로 구현했다. for (int i = start; i < N; i++) { if (visited[i]) continue; visited[i] = true; DFS(i + 1, depth + 1, sum + arr[i]); visited[i] = false; } } } | cs |
반응형
'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글
| [BOJ] 백준 2579 - 계단 오르기 (자바) (0) | 2018.05.03 |
|---|---|
| [BOJ] 백준 1194 - 달이 차오른다, 가자. (자바) (0) | 2018.05.01 |
| [BOJ] 백준 1003 - 피보나치 함수 (자바) (0) | 2018.04.30 |
| [BOJ] 백준 11720 - 숫자의 합 (자바) (0) | 2018.04.26 |
| [BOJ] 백준 15686 - 치킨 배달 (자바) (0) | 2018.04.16 |