Menu

Subscribe

[JAVA/백준] SW 역량 테스트 준비-기초 | 브루트 포스: 차이를 최대로

HEESOO on Boj

👀 문제

https://www.acmicpc.net/problem/10819

👊 도전

1. 설계

  1. DFS를 이용하여 모든 경우를 확인한 후, max를 저장한다.

2. 구현 (성공 코드)

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.util.Scanner;

/**
 * @author HEESOO
 *
 */
public class Main {
	static int n, max;
	public static void dfs(int[] array, int depth) {
		if(depth==n) {
			sum(array);
			return;
		}
		for(int i=depth;i<n;i++) {
			swap(array, i, depth);
			dfs(array, depth+1);
			swap(array, i, depth);
		}
	}
	public static void swap(int[] array, int i, int j) {
		int temp=array[i];
		array[i]=array[j];
		array[j]=temp;		
	}
	public static void sum(int[] array) {
		int sum=0;
		for(int i=1;i<n;i++)
			sum+=Math.abs(array[i]-array[i-1]);
		
		max=Math.max(max, sum);
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		n=scan.nextInt();
		int[] array=new int[n];
		max=0;
		for(int i=0;i<n;i++)
			array[i]=scan.nextInt();
		
		dfs(array, 0);
		System.out.println(max);
	}
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. DFS를 이용하여 모든 경우를 구한다
    • 처음에는 array[i]에 대해 array[j]를 모두 확인한 후 차이의 절대값이 가장 큰 경우를 찾는 방식으로 구현했는데, 그러면 예제 값이 틀리게 나와서 모든 경우를 다 구해야한다는 것을 깨달았다.
    • DFS를 이용하여 모든 경우를 확인한다.
    • 만든 배열로 sum을 구한 후, max보다 크다면 갱신한다.

👏 해결 완료!

참고