본문 바로가기

Algorithm/SWEA

[SWEA] D3. 정곤이의 단조 증가하는 수

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AWcPjEuKAFgDFAU4&categoryId=AWcPjEuKAFgDFAU4&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=PYTHON&select-1=3&pageSize=10&pageIndex=4&&&&&&&&&& 

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

 

 

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