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

 

📌문제

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

 

🎖️난이도

Level 3

 

✔️풀이

# 정답 (DP, Brute Force)
def solution(N, number):
    
    if N == number: return 1 # 마지막 테스트 케이스 주의! (같으면 연산자 X)

    set_list = [set([int(str(N)*(i+1))]) for i in range(8)]
    
    for i in range(1, 8):
        for j in range(i): 
            # 두 set의 product => 사칙연산 수행
            for num1 in set_list[j]:
                for num2 in set_list[i-j-1]:
                    set_list[i].add(num1 + num2)
                    set_list[i].add(num1 - num2)
                    set_list[i].add(num1 * num2)
                    if num2 != 0:
                        set_list[i].add(num1 // num2)
        
        if number in set_list[i]:
            return i+1
    
    return -1

 

🧠노트

DP의 탈을 쓴 Brute-Force 문제 같은 느낌이다.

 

N 1개로 표현 가능한 모든 수들을 set에 모조리 담고,

N 2개로 표현 가능한 모든 수들을 그 다음 set에 모조리 담고,

...

N 8개로 표현 가능한 모든 수들을 마지막 set에 담는다.

 

이 set들은 하나의 list에 담기도록 초기화 하고, for문을 돌며 한 set씩 계산해 나간다.

각 단계의 set를 구할 때에는, 이전에 구해 놓은 set들(DP) 중 2개씩 Product처럼 사칙연산을 모두 적용(B-F)해주면 된다.

 

이 문제는 효율성 채점하는 부분이 없기도 하니까, 

처음부터 '이게 될까..? 이게 맞나? 너무 오래걸리지 않나?' 걱정하며 다른 효율적인 코드 짜려고 하지 말고,
우선 "완전 탐색"으로 싹 다 구현을 시작해보자!

 

set는 정말 빠르다는 걸 새삼 느낀 문제... (add와 in을 저렇게 많이 했는데도 잘 돌아가다니!)

 

🔍참고

-