코딩테스트 준비

프로그래머스 (N으로 표현) with python

Grey Kang 2021. 3. 8. 22:36
반응형
  • 문제 설명

아래와 같이 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 합니다.

 

  • 솔루션

두 가지 방향성을 가지고 풀 수 있는 것 같다

  • 재귀를 통하여 나타내기(top-down(메모이제이션) 방식)
  • bottom-up 방식

top-down 풀이법

import math
def DP(level,result,target,array):
    if level<9: # 최솟값이 9보다 작을 떄
        if result in dic: # 사전 자료형에 정의되어 있는 key값을 이용
            if dic[result]>level: # value값이 더 클 때만
                dic[result]=level
                if result==target:
                    return level
                for i in range(8):
                    DP(level+i+1,result+array[i],target,array)
                    DP(level+i+1,result-array[i],target,array)
                    DP(level+i+1,result*array[i],target,array)
                    if array[i]!=0:
                        DP(level+i+1,result//array[i],target,array)
        else: # 초기 dictionary에 key값이 없을 때만
            dic[result] = level
            if result == target:
                return level
            for i in range(0, 8):
                DP(level+i+1,result+array[i],target,array)
                DP(level+i+1,result-array[i],target,array)
                DP(level+i+1,result*array[i],target,array)
                if array[i]!=0:
                    DP(level+i+1,result//array[i],target,array)
    
    # else: # 최솟값이 9보다 클 때


def solution(N, number):
    array=[0]*8
    temp=0
    for i in range(8):
        temp+=N*math.pow(10,i)
        array[i]=temp
    DP(0,0,number,array)
    if number in dic:
        return dic[number]
    else:
        return -1

top-down 재귀호출을 통하여 피보나치와 유사하게 위에서 아래로 계산을 해나가는 풀이법이다

코드를 설명해보자면 level이라는 것은 최솟값의 형태로 9보다 작아야 한다는 조건을 달아준다

위 구문에서는 사전형을 통하여 key값으로 result를, value값으로 해당하는 level을 넣어준다

이를 조건문을 통하여 최소의 조건일 때만 return 될 수 있도록 한다

초기에 solution을 정의할 때 level에 맞는 숫자의 개수를 담아준다

그리고 마지막으로 top-down 방식답게 재귀함수를 통해 사칙연산의 값을 실어주어 계산해준다

 

 

bottom-down 방식

def solution(N, number):
    # solution
    # 해당 level이 올라갈 때마다 level에 관한 값들을 모두 level을 키로 한 value값으로 넣어준다
    # 이전 레벨들끼리의 합을 통해 level을 만들어 그 값이 target과 일치할 경우 빠져나간다
    s=[set() for x in range(8)]
    for i,x in enumerate(s):
        x.add(int(str(N)*(i+1)))
    


    for i in range(0,8): # level 설정
        for j in range(i):
            for val1 in s[j]:
                for val2 in s[i-j-1]:
                    s[i].add(val1+val2)
                    s[i].add(val1-val2)
                    s[i].add(val1*val2)
                    if val2!=0:
                        s[i].add(val1//val2)
        if number in s[i]:
            return i+1

위의 top-down에 비해 훨씬 간단하다

이 solution의 경우, 앞선 풀이와는 조금 다르게 level을 정의할 때 이전 level들과의 합이 level에 정의될 수 있다는 것을 이용한다 즉

5+5=10에서 10은 level=2인 값이다

5+5+5=15이다 이 때 level=3이 된다

이 때 level=2인 값과 level이 1인 값의 합으로 15라는 값이 탄생한 것을 알 수 있다

이를 이용한 풀이법이 위와 같다

 

각 level마다 할당되는 값들을 다 넣어주고 해당 값들을 이용하여 다음 level의 값들을 알아낸다

이 후, level들 중 target값과 동일한 값이 있으면 바로 return 해주면 된다

 

반응형