N으로 표현 (프로그래머스 Lv3 동적프로그래밍)

문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항

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

입출력 예

Nnumberreturn

5	12	4
2	11	3

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

출처

※ 공지 - 2020년 9월 3일 테스트케이스가 추가되었습니다.

 

 

def solution(N, number):
    case_d = {
        str(N)*1 : set(),
        str(N)*2 : set(),
        str(N)*3 : set(),
        str(N)*4 : set(),
        str(N)*5 : set(),
        str(N)*6 : set(),
        str(N)*7 : set(),
        str(N)*8 : set(),
        }
    
    for key in case_d.keys():
        case_d[key].add(int(key))
        if int(key) == number: # 새로운 테스트 케이스로 추가한 if문.
            return len(key) 
        for num in list(range(1, len(key))):
            a,b = str(key)[0:num], str(key)[num:]

            for i in case_d[a]:
                for j in case_d[b]:
                    case_d[key].add(i + j)
                    case_d[key].add(i - j)
                    case_d[key].add(i * j)
                    if j != 0:
                        case_d[key].add(i // j)
                if number in case_d[key]:
                    return len(key)

    return -1

 

아래는 좀 난잡하지만 문제의 예시에서 N이 5일 때 자리수를 하나씩 늘려가면서 만들 수 있는 조합으로 얻는 결과들의 집합을 노란색 선으로 표시하였다. 자리수가 3~4개까지는 손으로 적을만한데 5자리부터는 손으로 적기에는 무리가 있다. 

자리수를 늘려갈 때마다 가능한 조합들은 이전의 만들었던 조합을 계속 이용하는 방식이기 때문에 이전에 만들었던 조합들의 조합을 for문으로 구성해서 풀면된다...2시간도 넘게 걸렸다. 시간제한이 있는 코딩테스트는 나랑 너무 안맞는 것 같다. 그런데도 해야한다. 하고 싶은걸 하려면 ... 하기 싫은거를 이렇게 해야한다... 에휴... 😖