2529. [Python]부등호

1. 문제

 

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

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 256MB
• 백트래킹
• 브루트포스

 

3. 파이썬 코드

 

# 백트래킹
def backtracking(index, check):
    # 인덱스가 끝값에 도달할 경우
    if index == K + 1:
        answer.append("".join(map(str, check)))
        return
    # 0 ~ 9 까지 값 반복하며 방문헀는지 안했는지 및 부등호에 따른 연산자 처리
    for num in range(10):
        if not visited[num]:
            if index == 0 or (operator[index - 1] == "<" and check[-1] < num) or (operator[index - 1] == ">" and check[-1] > num):
                visited[num] = True
                backtracking(index + 1, check + [num])
                visited[num] = False


K = int(input())
operator = input().split()

visited = [False] * 10
answer = []
# 방문처리 및 리스트 정리
for num in range(10):
    visited[num] = True
    backtracking(1, [num])
    visited[num] = False

print(answer[-1])
print(answer[0])

 

4. 문제를 풀고난 후 생각

 

• K 값이 2 ~ 9 이므로 백트래킹 + 브루트 포스로 모든 경우의 수를 돌아가며 가능한 부등호 경우의 수를 모두 저장한다.
• 0부터 시작했기 때문에 0 번인덱스가 최소값 -1 인덱스가 끝값이 되므로 백트래킹 구현만 제대로해주면 쉽게 풀 수 있다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 브루트 포스
• 백트래킹