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

사용 언어 - Python3

문제 - N으로 표현

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

프로그래머스

 

 

 

정답

n숫자를 이용해서 number를 만들기

n 숫자를 1개부터 8개(cnt)까지 활용하면서 찾아준다.

 

n을 최소한으로 사용해야하므로 number 값이 나오면 바로 끝낸다. return cnt

 

구하는 값 저장할 리스트, dp = []

dp 값들로 사칙연산한 값을 저장할 set, partial_dp = set()

n을 2번 사용한다 = n + n or nn

n이 연속으로 오는 경우도 있으므로 str(N)*cnt 로 묶어준다.

partial_dp.add(int(str(N)*cnt)

 

for문 구조

n 1개로 할 수 있는 모든 연산 n+n, n*n, n-n, n/n => partial_dp에 추가 => dp에 추가
n 2개로 할 수 있는 모든 연산 앞서 구한 값들 dp(n+n, n*n, n-n, n/n) + nn => partial_dp에 추가 => dp에 추가

n 3개로 할 수 있는 모든 연산 앞서 구한 값들 dp(n+n, n*n, n-n, n/n, nn) + nnn => partial_dp에 추가 => dp에 추가

....

 

출력

partial_dp에 찾고자하는 number가 있다면

해당 cnt 값을 return 한다!

 

예외

number = 1이라면 무조건 정답은 1 return 1

n을 8번까지 사용했는데도 number 값을 찾지 못했다면 return -1

 

# n 숫자만을 이용한 사칙연산으로 number를 만들어야함
def solution(N, number):
    if number == 1:
        return 1
    dp = []
    
    # 1부터 8까지 n을 사용하자
    for cnt in range(1,9):
        partial_dp = set()
        partial_dp.add(int(str(N) * cnt)) # 이어 붙여서 만드는 경우 N, NN, NNN, ... 
        for i in range(cnt - 1): # n을 1만 사용하고 연산 ~ 7만 사용하고 연산
            for op1 in dp[i]:
                for op2 in dp[-i - 1]:
                    partial_dp.add(op1 + op2)
                    partial_dp.add(op1 * op2)
                    partial_dp.add(op1 - op2)
                    if op2 != 0:
                        partial_dp.add(op1 / op2)
        # 만든 집합에 number가 처음 나오는지 확인
        if number in partial_dp:
            return cnt
        dp.append(partial_dp)
    # n을 8번까지 사용했는데도 number를 만들지 못한 경우
    return -1

 

 

 

 

레퍼런스

• 정답 깃허브