728x90
반응형
문제 출처 :
문제 풀이 :
- 문제를 분할해서 생각해보자.
- 새로 추가되는 숫자에 대한 부등호 관계가 만족하는가?
- 새롭게 추가되는 숫자를 중복없이 어떻게 만들 것인가?
- 최소와 최대를 어떻게 구할 것인가? (따로 구분해주기)
- 위의 서브 문제들을 풀어가보자
- 새로운 숫자가 추가 될때 마다 앞에 숫자랑 비교해주는 함수를 만들자(check 함수)
- 백트래킹을 이용해보자. 숫자는 중복없이 0~9까지이므로 for문 돌려서 사용하면된다.
- 이때 어차피 check에서 안되는 건 따로 만들 필요없으므로 가지치기를 진행해준다.
- 만약 조건에 부합한 문자열이 처음 생긴거면 그게 제일 작은 거다. 그리고 제일 마지막에 구해진 녀석이 제일 큰 녀석이다 (애초에 시작할때 0부터 커지는 순서로 for문을 돌렸으니까.)
n = int(input())
ine_sing = list(map(str,input().split()))
visited = [0]*10
max_ans =""
min_ans =""
def check(i,j,k):
if k=='<':
return i<j
else:
return i>j
def solve(idx,s):
global max_ans,min_ans
if(idx==n+1):
if(len(min_ans)==0):
min_ans = s
else:
max_ans = s
return
for i in range(10):
if(visited[i]==0):
if(idx==0 or check(s[-1],str(i),ine_sing[idx-1])):
visited[i]=True
solve(idx+1,s+str(i))
visited[i]=False
solve(0,"")
print(max_ans)
print(min_ans)
반응형
'Computer Science > Algorithm' 카테고리의 다른 글
[백준] 2805 - 나무 자르기(Python) (0) | 2021.04.02 |
---|---|
[백준] 2869 - 달팽이는 올라가고 싶다 (Python) (0) | 2021.04.02 |
[백준] 2217 - 로프 (Python) (0) | 2021.03.30 |
[백준] 1931 - 회의실 배정 (Python) (0) | 2021.03.27 |
[백준] 11053 - 가장 긴 증가하는 부분 수열 (C++) (0) | 2021.03.26 |