[C++] 백준 10819번 차이를 최대로

백트래킹 문제.

N의 크기가 3부터 8이다.

따라서 최대 경우의 수가 8! 이므로 40,320번 안에 모든 탐색을 마칠 수 있다.

 

처음에 부등호를 잘못 표기해서 틀렸습니다. 를 받았다.

백트래킹인 것을 알고서 접근하면 어려운 문제는 아니다.

 

문제풀이

문제 그대로 구현해주면 된다.

순차적으로 가능한 모든 배열의 경우의 수를 만들어서 그 중 최대값을 골라서 갱신하면 된다.

 

어려운 부분은 없으므로 바로 코드로 설명하겠다.

사용한 STL과 변수

vector를 사용하기 위한 vector STL,

max() 메서드 사용을 위한 algorithm,

절대값 abs() 메서드 사용을 위한 math.h를 사용했다.

 

• numCnt : 배열에서의 숫자의 개수
• arr 배열 : 처음에 입력받는 숫자들을 저장할 배열
• visit 배열 : 백트래킹 메서드를 할 때, 배열에서 해당 idx의 원소를 탐색했는지 확인하는 메서드
• vec 벡터 : 백트래킹을 할 때 A[0], A[1], A[2], ...원소를 순차적으로 담을 배열
• answer : 차이의 최대값을 저장할 변수

 

메인함수

처음에 숫자의 개수를 입력받고 숫자의 개수만큼 원소를 입력받는다.

그리고 for문으로 각 원소가 첫번째 값이 되게 하도록 백트래킹 메서드를 시작한다.

 

백트래킹 작업이 모두 끝났다면, 결과값을 출력한다.

 

백트래킹 메서드

매개변수로 현재 몇번째 수를 넣을 것인지에 대한 정보인 idx 변수를 받는다.

 

만일 idx 변수가 numCnt(원소의 개수)를 넘었다면, 이미 다 채워졌다는 뜻이다. 후에 아래의 작업을 수행한다.

• 원소를 순차적으로 담은 vector변수에서 문제의 조건에 맞게 더해서 값을 구한다.
• 현재 저장된 값인 answer와 비교해서 더 큰 값을 저장한다.

아니라면, 아직 더 넣어줄 값이 있다는 뜻이다.

visit 배열로 넣지 않은 값들만 넣어서 진행한다.

이 for문에서 i < numCnt라고 적어서 한 번 틀렸다.

아무래도, 배열은 1부터 벡터는 0부터 접근하므로 헷갈린 것 같다..

 

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인이 가능하다.