[Python] Lv3. N으로 표현

https://school.programmers.co.kr/learn/courses/30/lessons/42895

프로그래머스

 

DP 문제의 특성으로는 제한사항을 특별히 꼼꼼히 읽어봐야 하는 점이 있다.

 

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

 

카테고리부터 DP이기 때문에 DP로 풀어보려고 노력했다. 일단 혼자 풀어보는 것은.. 실패했다.

그 이유는 시작할 때  캐싱 배열을 어떻게 설정할지부터 잘 모르기 때문이었다.

 

그래서 도움을 받아 떠올린 배열은 아래와 같다.

• 카운트가 8번까지로 제한
• 카운트 별 나올 수 있는 값들을 모으는 배열이 필요
• set() 함수를 사용해서 카운트 별 나올 수 있는 값들을 중복 제거한 배열 설정

이 배열에 나올 수 있는 값들을 모두 dp 배열에 넣고, 첫번째 인덱스(카운트 1)부터 찾아보면서 해당 숫자가 나타날 때, 그 인덱스를 반환하는 것이 문제의 핵심이다.

def solution(N, number):
    # 최솟값이 8보다 큰 경우 -1을 반환
    INF = 8
    # N을 사용한 횟수를 저장하는 배열
    dp = [set() for _ in range(INF + 1)]

    # 숫자 N을 사용하는 횟수 초기화
    for i in range(1, INF + 1):
        dp[i].add(int(str(N) * i))

    # 사칙연산을 활용하여 number를 만들 수 있는지 확인
    for i in range(1, INF + 1):
        for j in range(1, i):
            for x in dp[j]:
                for y in dp[i - j]:
                    dp[i].add(x + y)
                    dp[i].add(x - y)
                    dp[i].add(x * y)
                    if y != 0:
                        dp[i].add(x // y)

        # number를 만들었을 때의 횟수가 i와 같다면 해당 횟수 반환
        if number in dp[i]:
            return i

    # 최솟값이 8보다 큰 경우 -1 반환
    return -1