수(기타) 놀이터

|

문제 코너

|

제출 현황

|

수학 Q/A

|

수학 quiz

|

koi 부등식 대회 풀이

(해법 1)

먼저 최대 순열을 구하는 방법을 보자. 

우선 9를 최대한 앞쪽에 배치하는 것이 관건이다. 

가장 먼저 오는 부등호가 ‘>’일 경우는 9xxxx..의 순열이 가능하기에 제일 앞에 9를 배치할 수 있다. 

반대로 가장 먼저 오는 부등호가 ‘<’일 경우는 제일 앞에 9가 오는 순열은 불가능하기에 가장 먼저 부등호 ‘>’이 오는 위치를 알아본다. 

예를 들어, < < > .. 일 경우는 세 번째 위치에 부등호 ‘>’이 나오므로 7 < 8 < 9 > ... 로 배치하는 것이 가장 최대 순열이 된다. 7, 8, 9를 배치했으므로 이제는 0 ~ 6의 숫자를 써서 최대 순열을 구하는 문제로 줄어들게 된다. 재귀적으로 이 방법을 적용하면 마지막까지 배치가 가능하다.

최대 순열을 구하는 것과 비슷한 방법으로 최소 순열을 구할 수 있다. 최소 순열일 경우는 부등호는 ‘<’이 앞에서 언제 나오는지 보고 0부터 채워 넣으면 된다.

이렇게 해결할 경우 시간 복잡도는 O(k)이다.

(해법 2)

재귀적인 방법으로 조건을 만족하는 가능한 모든 경우의 순열을 만들어 나가면서 수의 값이 최대인 경우와 최소인 경우를 저장한다. 

이 방법은  의 시간복잡도를 가지게 되는데 k의 최대값이 9로서 매우 작으므로 적당히 제약조건을 주며 퇴각검색(backtracking)을 하면 제한 시간 내에 충분히 해를 찾는 것이 가능하다.