1. 해결방법
이 문제도 재귀 완전탐색으로 해결해보려 했지만 테스트 케이스 50개중 42개만 통과하였다.
재귀로는 30분 정도 걸렸다.
시간 초과 문제를 해결하기 위해서 재귀를 도는 시점에서 i, j의 곱의 결과를 바로 단조인지 체크하는 로직을 구상하였다.
1. 두 수의 곱이기에 두 수의 곱이 될때까지 완전 탐색을 한다.
2. 두 수의 곱이 나왔을 때 재귀를 리턴해야하는데, 그 전에 for문을 돌아서 각 숫자가 단조인지 체크한다.
3. 단조라면 최댓값 answer를 갱신한다. 그게 아니라면 answer의 초기값이 -1이기에 값을 새로 갱신하지 않는다.
2. 정답코드
def dfs(idx, count, num):
global answer
if count == 2:
num_string = str(num)
for k in range(len(num_string) - 1):
if num_string[k] > num_string[k + 1]:
break
else:
answer = max(answer, num)
return
for j in range(idx, N):
if chk[j] == False:
chk[j] = True
dfs(idx + 1, count + 1, num * numbers[j])
chk[j] = False
T = int(input())
# T = 1
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
N = int(input())
numbers = list(map(int, input().split()))
chk = [False] * N
result = []
answer = -1
for i in range(N):
if chk[i] == False:
chk[i] = True
dfs(i + 1, 1, numbers[i])
chk[i] = False
print(f"#{test_case} {answer}")
'Algorithm > SWEA' 카테고리의 다른 글
[SWEA] D4. 준환이의 양팔저울 (0) | 2023.01.03 |
---|---|
[SWEA] D.3 0/1 Knapsack (0) | 2022.11.19 |
[SWEA] D3. 오목 판정 (0) | 2022.11.17 |
[SWEA] D3. 최장 증가 부분 수열 (0) | 2022.11.17 |
[SWEA] D3. 재미있는 오셀로 게임 (0) | 2022.11.14 |