[DP] 프로그래머스 level 3 N 으로 표현 Python 풀이

 

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

프로그래머스

문제 접근

• N을 1개 사용해서 할 수 있는 표현은 5
• N을 2개 사용해서 할 수 있는 표현은 55, 5+5, 5-5, 5*5, 5/5
• N을 3개 사용해서 할 수 있는 표현은 555, 55 + 5, 55 - 5, 55 * 5, 55 / 5, 5 + 5 + 5, 5 - 5 - 5, 5 / 5 / 5, 5 * 5 * 5
• 일반화 해보면

n번 이어 붙여서 만든 수 
1번 사용해서 표현한 수 집합 (사칙 연산) n - 1 번 사용해서 표현한 수 집합
2번 사용해서 표현한 수 집합 (사칙 연산) n - 2 번 사용해서 표현한 수 집합
                    	.
                        .
                        .
                    
n - 1번 사용해서 표현한 수 집합 (사칙 연산) 1 번 사용해서 표현한 수 집합
출처: https://alreadyusedadress.tistory.com/115 [ :티스토리]

• 중복 제거를 위해 set() 자료구조를 하나 만들고, 모든 숫자를 저장하는 리스트 하나를 선언
• 문제 조건에서 9개 부터는 -1 리턴이므로 1 ~ 8개의 N으로 만들 수 있는 수들 중에서 number가 처음 나오는 개수를 리턴

코드

def solution(N, number):
    if number == 1:
        return 1
    possible_num = []

    for i in range(1, 9): 
        current_num = set()
        current_num.add(int(str(N) * i)) # {555}
        for j in range(i - 1): # (1, 2), (2, 1)
            for num1 in possible_num[j]:
                for num2 in possible_num[-j - 1]:
                    current_num.add(num1 + num2)
                    current_num.add(num1 * num2)
                    current_num.add(num1 - num2)
                    if num2 != 0:
                        current_num.add(num1 / num2)
        
        if number in current_num:
            return i
        possible_num.append(current_num)
    return -1

참고 자료

https://alreadyusedadress.tistory.com/115

[프로그래머스] N으로 표현 - python