[2012년 초등부 정올 지역본선, BOJ 2529] 부등호

오랜만입니다.

 

PS연습을 다시 시작해서 감을 살리려고, boj에서 알고리즘 분류 별로 나누어진 카테고리를 들어갔는데, 이 문제가 왜인지 눈에 밟혔다. 문제는 여기

 

초등부 정올 문제였다고 하는데, 언뜻 봐서는 잘 방법이 떠오르지 않았다. 대충 그리디하게 하면 될 것 같은데...하는 생각을 하고 있었다.(사실 문제 분류도 그리디였다.)

 

그런데 의외로 그게 이런저런 케이스들도 생각 많이 해줘야 하고, 못할 것 같지는 않아서 어려울 거라고 생각했는데, 어차피 10!은 해봐야 4백만도 안되고, 그냥 완전탐색으로 해봐도 괜찮을 것 같았다.

 

결국 구현의 문제였고, 파이썬에는 itertools 모듈이 있어서 구현을 아주 간편하게 할 수 있었다.(만약 그렇지 않았더라면 아마 백트래킹으로 모든 경우를 찾는 게 가장 어려운 구현이 됐을 것이다.)

 

풀이는 다음과 같이 하면 된다. C++ 구현은(개강하느라 바빴기 때문에)나중에 생각해봐야 할 것 같다.

import itertools
k=int(input())
L=input().split()
def check(L, numbers):
    for i in range(len(L)):
        if L[i]=='<'and numbers[i]>numbers[i+1]:return False
        if L[i]=='>'and numbers[i]<numbers[i+1]:return False
    return True #만들어진 경우가 부등호 배열에 맞는 건지 체크하는 함수

def tupleint(a):
    s=''
    for i in a:s=s+str(i)
    return s #itertool의 permutations는 안에 tuple들이 들어가 있다. 이 tuple을 int로(사실 함수명은 그런데 실질적으로는 str로다)바꾸어주는 함수이다.
maxn=0
minn=999999999999
for i in itertools.permutations(range(10),k+1): #그냥 정직하게 모든 경우 다 해본다.
    if check(L, i):
        s=tupleint(i)
        m=int(s)
        if m>int(maxn):maxn=s
        if m<int(minn):minn=s
print(maxn)
print(minn)