BOJ(부등호)(2529)

작성일 | In
  • 순열 사용하기

부등호 2529

  • 부등호 기호 ‘<’ 와 ‘>’가 나열된 수열 A가 있다.
  • 부등호와 부등호 사이에 한 자리 숫자를 넣어서, 모든 부동호 관계를 만족시키는 값을 찾으려고 한다.
  • 부등호를 만족한다는 것은 동시에 만족할 필요는 없고, 따로따로 만족하면 된다.
  • 선택한 수는 모두 달라야 한다는 조건이 있다.

  • k개의 부등호 관계를 모두 만족시키는 (k+1)개의 정수 중에서 최대값과 최소값을 구하는 문제

  • ex) 2 < 5 > 4, 2< 9 > 4 등등

  • 2<9>4 라고 해보자. 4,7,8을 여기에 넣는다면 경우의 수는 ? 3!가지.

  • 어떤 수가 올껀지 말껀지만 잘 확인해보면 된다. 순열을 사용해서 해결해볼 수 있다.

  • 순열을 사용하기 전에 어떤 수를 먼저 써야할지 결정하고, 그 다음에 순열을 사용해야 한다.
  • 순열을 한번만 사용하는게 아니다. 수의 개수는 k+1개니까. (k+1)!의 순서가 제시되겠지만,
  • 어떤 수를 넣어야 할지도 결정을 해줘야 한다.
  • 최댓값과 최솟값만 구하라고 했기 떄문에, 순열로 풀 수 있다.
  • 최댓값은 987654, - > 987로만
  • 최솟값은 012345- > 0123로만.
  • 그래서 한번씩만 순열을 돌려보면 문제를 풀 수 있다.

def next_permutation(a):
    i = len(a)-1
    while i > 0 and a[i-1] >= a[i]:
        i -= 1
    if i <= 0:
        return False
    j = len(a)-1
    while a[j] <= a[i-1]:
        j -= 1

    a[i-1],a[j] = a[j],a[i-1]

    j = len(a)-1
    while i < j:
        a[i],a[j] = a[j],a[i]
        i += 1
        j -= 1

    return True

def prev_permutation(a):
    i = len(a)-1
    while i > 0 and a[i-1] <= a[i]:
        i -= 1
    if i <= 0:
        return False
    j = len(a)-1
    while a[j] >= a[i-1]:
        j -= 1

    a[i-1],a[j] = a[j],a[i-1]

    j = len(a)-1
    while i < j:
        a[i],a[j] = a[j],a[i]
        i += 1
        j -= 1

    return True

def check(perm, a):
    for i in range(len(a)):
        if a[i] == '<' and perm[i] > perm[i+1]:
            return False
        if a[i] == '>' and perm[i] < perm[i+1]:
            return False
    return True

k = int(input())
a = input().split()
small = [i for i in range(k+1)]
big = [9-i for i in range(k+1)]

while True:
    if check(small,a):
        break
    if not next_permutation(small):
        break
while True:
    if check(big, a):
        break
    if not prev_permutation(big):
        break

print(''.join(map(str,big)))
print(''.join(map(str,small)))
  • 백트래킹으로 푸는게 현실적으로 더 나아보이지 않을까 ( 위 코드는 백준님 코드다)
def is_Safe(x, y, op):
    if op == '<':
        if x > y:
            return False
    if op == '>':
        if x < y:
            return False
    return True


def dfs(idx, num):
    if idx == n+1:
        ans.append(num)
        return
    for i in range(10):
        if not check[i] and (idx == 0 or is_Safe(num[idx-1], str(i), a[idx-1])):
            check[i] = True
            dfs(idx+1, num+str(i))
            check[i] = False

n = int(input())
a = input().split()
ans = []
check = [False] * 10
dfs(0, '')
ans.sort()
print(ans[-1])
print(ans[0])
  • 매개 변수 ‘‘를 활용해서 global result 사용하지 않고도 구할 수 있다.

백준님 코드

  • 부등호 문제는 순열로 푸는게 비효율적이다.

  • 앞에서부터 끊어서 풀 수 있기 때문이다.(조건이 위배하는게 발견되었을 경우, 바로 return으로 종료가능)

참고자료 codeplus

0%