[Algorithm]백준, 10819, 차이를 최대로

문제:www.acmicpc.net/problem/10819

 

비고:

-Brute force

-다 세지 않고선 규칙을 발견하기 힘들며, 영역 나누기도 힘들어 보이며, 주어진 조건이 가용 시간/메모리 내에 해결 가능

-이런 문제에서 모든 경우를 세기 위해서 next permutation함수를 잘 짜야 한다.

-입력받은 list을 next permutation으로 바꾸며, return은 True/False로 작성

-next permutation을 처음작성하는 거라면 난이도가 있다.

  -기본 규칙은, 배열의 index 0부터(=좌측부터) 우측으로 훑으며 "마지막" 증가(increase)인 index(i)를 찾는다.

  ex) 124653에서 46가 마지막 증가(<)고 4의 index인 2

  -마지막 증가에서의 값보다 크며 가장 우측에 존재하는 값의 index(j)를 찾는다.

  ex) 124653에서 65중에서 5가 더 오른쪽, 5의 index인 4

  -i,j에서의 값 교환

  ex) 124653 -> 125643

  -j보다 우측의 값들을 정렬시킨다.

-난이도중

 

내소스코드:

boj.kr/33b0cb84fe5d4b48b02c860081023606