백준 10819번 ☆

문제

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

10819번: 차이를 최대로

import java.util.Scanner;

public class Main10819 {
	
	public static int N;
	public static int[] A;
	public static int[] B;
	public static boolean[] check;
	public static int answer;
	
	public static void compare(int n) {

		int sum = 0;
		
		if (n==N) {
			for (int i=0; i<N-1; i++) {
				sum += Math.abs(B[i]-B[i+1]);
			}
			answer = Math.max(answer, sum);
			
		} else {
			for (int i=0; i<N; i++) {
				if (!check[i]) {	
					B[n] = A[i];
					check[i] = true;
					compare(n+1);
					check[i] = false;
				}
			}
		}	
	}

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		A = new int[N];
		B = new int[N];
		check = new boolean[N];
		
		for (int i=0; i<A.length; i++) {
			A[i] = sc.nextInt();
		}	
		
		sc.close();
		compare(0);	
		
		System.out.println(answer);
	}
}

 

1. 틀린것을 넘어서 어떻게 접근을 해야할지 생각조차 못했다. 

 

2. 하루종일 끙끙거리다 포기하고 오늘 do it 알고리즘을 공부하다가 재귀함수에 관한 내용이 나왔다. 읽다보니 이 방식이구나 싶었다라고 생각이 들었는데 막상 적용해보려하니 쉽지 않았다.

 

3.  구글링을 통해 내가 생각한 방식과 가장 유사한 글을 찾았다.

https://codingrapper.tistory.com/27

[BOJ - JAVA] 10819 - 차이를 최대로(완전탐색, 백트래킹)

덕분에 좋은 공부가 됐습니다..감사합니다..

 

4. 포인트는 6가지의 수가 입력될 경우 6!의 경우의 수를 비교해야하는데 for문으로만 접근하려니 쉽지 않았던 것이다. 그래서 재귀함수를 사용해 모든 경우의 수를 만들어야한다. 

 

5. 아직 재귀함수가 머릿속에서 명확하게 그려지는것은 아니다. 하지만 이런 방식이 있다는것을 통째로 외워서 사용하다보면 분명 명확히 이해하는 날이 온다 믿는다..

 

* 온전히 내 힘으로 풀지 못한 문제는 제목에 '☆' 표시 후 며칠 뒤 다시 풀어볼 것