[BOJ] 10819번: 차이를 최대로 / JAVA / Backtracking, BruteForce

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

10819번: 차이를 최대로

 

 

* 풀이 방법

1. 모든 배열을 구해본 후

2. 배열의 차이, abs의 합계의 최대값을 비교한다. 

 

* 나는 왜 백트래킹으로 접근했는가?

- 우선 모든 배열의 순열을 구한 후에, 아닌 경우 다시 뒤돌아가서(BACK) 구해야 했기 때문에, 백트래킹으로 풀어야 한다고 판단. 

 

 

< 나의 풀이>

 

 

 

===========================내가 나중에 다시 확인하려고 적어두는 내용들===============================

< 리뷰 !  풀면서 헷갈렸던 부분 3가지 > 

1. ans = Math.max(ans,sum) 을 어디서 비교할건지?

- 처음 main함수안에서 ( for문 뒤에 solve하고 ) 비교했더니, solve함수가 끝나는 지점에서만 tmp를 넘겨주기때문에 의미가 없었다.

-> 따라서 solve함수안에서 결과가 끝났을때, ans 최대값을 비교해서 계속 가지고 있어야 마지막에 return해도 최대값을 받을 수 있다.

 

2. 백트래킹과 같은 재귀함수는 return 은 void 형태 즉 리턴값은 없다.

- 계속해서 solve 함수는 solve 함수를 호출하고.. 또 호출하기 때문에 int를 계속 반환할 수 없다.

 

3. 맨 처음 check[now] = true를 어디서 해줄 것인지?

 1) solve 함수 전에 체크해주고 그 뒤에 체크 해제 해야하는가? 

2) solve 함수 호출할때 check[now]= true를 해주어야 하는걸까? 

- 제일 처음 이렇게 접근했었는데, 이미 앞부분에서 check[now]를 해주면 뒷부분에서 check=true라서 확인을 못하는 부분이 생긴다.

ex. solve(0,0,0) 에서 시작하면, check[0]= true가 된다. 

  ----> solve(4,0,0) 을 시작하려고 하면 이미 check[0]= true 인 상태에서 진행하게된다.

 

따라서, 함수 내에서 check[idx]= true 를 하는 것은 지양하는게 좋을 것 같다.