https://swexpertacademy.com/main/solvingProblem/solvingProblem.do
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
코드
def solution(numbers,cnt): global result # 숫자를 저장할 빈 문자열 생성 tmp = '' for number in numbers: tmp += number # 이 교환횟수에서 이미 만들어진 적 있는 숫자라면 리턴해서 실행시간 단축 if int(tmp) in result[cnt]: return # 처음 만들어진 숫자라면 정수형으로 바꿔서 리스트에 추가 else: result[cnt].append(int(tmp)) # 교환횟수를 다 소진했다면 리턴 if cnt==0: return length = len(numbers) # 두 숫자의 자리를 교환하고 dfs 탐색을 진행한 뒤 원상복구 for i in range(length): for j in range(i+1,length): numbers[i],numbers[j] = numbers[j],numbers[i] solution(numbers,cnt-1) numbers[i],numbers[j]=numbers[j],numbers[i] T = int(input()) for test_case in range(1, T + 1): # 숫자와 교환횟수를 입력받음 n, chance = input().split() # 자리수교환을 편하게 하기 위해서 리스트로 변경함 numbers = list(n) # 남은 교환횟수별로 만들어진 숫자를 저장하는 리스트 생성 result = [[] for _ in range(int(chance)+1)] solution(numbers,int(chance)) # 교환횟수를 모두 소진했을 때 만든 숫자 중 가장 큰 것을 출력 print('#{} {}'.format(test_case,max(result[0])))
후기
- 남은 교환횟수를 깊이로 DFS 탐색을 해서 풀어내는 것이 인상적이었다.
'Algorithm > [SWEA] - Python' 카테고리의 다른 글
[SWEA/D3] 5215 : 햄버거 다이어트 python (0) | 2023.11.17 |
---|---|
[SWEA] 1213 : [S/W 문제해결 기본] 3일차 - String python (0) | 2023.11.05 |
[SWEA] 1206 : [S/W 문제해결 기본] 1일차 - View python (0) | 2023.10.01 |
[SWEA/D3] 16800 : 구구단 걷기 python (0) | 2023.09.09 |
[SWEA/D4] 2819 : 격자판의 숫자 이어 붙이기 python (0) | 2023.09.09 |