[백준][파이썬] 2529번 부등호

 

 

부등호 성공출처분류

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

256 MB

10238

5175

3618

49.024%

문제

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열  A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. 

A =>  < < < > < < > < >

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다. 

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다. 

입력

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다. 

출력

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. 

예제 입력 1 복사

2 < >

예제 출력 1 복사

897 021

출처

Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2012 > 초등부 5번

알고리즘 분류

• 그래프 이론
• 브루트포스 알고리즘
• 백트래킹
• 위상 정렬

https://www.acmicpc.net/problem/2529

2529번: 부등호

 

2529번: 부등호

오랜만에 문제를 풀었더니... 정말 많이 잊어버렸다.. 앞으로는 하루에 한문제씩 꾸준히 풀어나가는 습관을 갖도록!

 

대표적인 BF 문제이다. 생각의 흐름은

1. 가능한 경우를 재귀함수로 돌리고 (N과M 처럼)

2. 가능한 경우를 체크한다.

3. 처음 만들어지는 수가 최소이고 마지막 수가 최대일것이다.

-> 재귀함수를 끊는 IF 부분에서 조건을 다는 경우가 대부분이였는데 자연스럽게 최대 최소를 구하는 방법도 고려하자! 

 

사실 모든 경우를 체크하는 재귀함수를 만드는 방법은 여러가지가 있다. 나는 주로 리스트를 만들어서 append와 pop을 활용했다. 하지만, 참고해서 작성한 아래의 코드처럼 문자열을 활용하는 방식이 시간 측면에서 훨씬 효율적인것 같다. 

 

 

num = int(input())
op = input().split()
check = [False] * 10
mx , mn = "",""
def poss(i,j,k): # 부등호 조건이  만족할 때만 작동
    if k == ">":
        return i>j
    else:
        return i<j


def recu(cnt, s):
    global mx,mn
    if cnt > num: #맨처음 나타나는 값이 최소, 마지막 저장되는 것이 최대
        if len(mn) == 0:
            mn = s
        else:
            mx = s
        return
    for i in range(10): #재귀 함수
        if check[i] == False:
            if cnt == 0 or poss(s[-1],str(i),op[cnt-1]):
                check[i] = True
                recu(cnt+1,s+str(i))
                check[i] = False

recu(0,"")
print(mx)
print(mn)

 

참고한 코드

https://hjp845.tistory.com/128

백준 2529 파이썬 python : 부등호 @@황소처럼 우직하게@@ 아직 멍청이다