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

N으로 표현

프로그래머스

 

 

• 다른 사람 풀이
  • N을 숫자 1개로, 2개로, 3개로....M( 1<M<N-1 )개로 표현
  • M개 사용하여 나올 수 있는 값들을 case_set에 모은 뒤 possible_set[M]에 저장
    • 계속  값들끼리 사칙연산 실행하면서 나올 수 있는 값들을 모두 구하는 것
  • 찾는 값이 case_set에 있으면 몇개를 사용한 것인지 M을 반환

 

def solution(N, number):
    possible_set = [0,[N]] # 조합으로 나올수 있는 가능한 숫자들, 여기에 계속 append하며 이후에 사용함
    if N == number: #주어진 숫자와 사용해야 하는 숫자가 같은 경우는 1개면 족하므로 1으로 놓는다. 
        return 1
    for i in range(2, 9): # 2부터 8까지로 횟수를 늘려 간다. 
        case_set = [] # 임시로 사용할 케이스 셋, 각 I 별로 셋을 만들어 possible set에 붙인다.
        
        basic_num = int(str(N)*i) # 같은 숫자 반복되는 거 하나를 추가한다. ("NN","NNN"...)
        case_set.append(basic_num)
        
        for i_half in range(1, i//2+1): # 사용되는 숫자의 횟수를 구해야 하는데, 절반 이상으로 넘어가면 같은 결과만 나올 뿐이므로 절반까지만을 사용한다. 
            for x in possible_set[i_half]:
                for y in possible_set[i-i_half]: # x와 y를 더하면 i 가 되도록 만든 수다. 
                    
                    case_set.append(x+y)# 각 사칙연산 결과를 더한다.
                    case_set.append(x-y)
                    case_set.append(y-x)
                    case_set.append(x*y)
                    if y !=0:
                        case_set.append(x/y)
                    if x !=0:
                        case_set.append(y/x)
                    
            if number in case_set:
                return i
            possible_set.append(case_set) # 최종 결과물 set에 사칙 연산 결과를 더한다.
    return -1 #N 이 8까지 답이 없으면 -1을 출력한다.

풀이 출처) https://www.hamadevelop.me/algorithm-n-expression/

프로그래머스-N으로 표현, 파이썬

 

• 다른 사람 풀이 2
  • 시간이 조금 더 단축

def solution(N, number):
    dp = [set() for i in range(9)] # 사용횟수에 따라 가능한 숫자를 담을 리스트
    for i in range(1, 9): # 1~8
        dp[i].add(int(str(N)*i)) # 단순히 이어붙인 숫자
        for j in range(i//2 + 1):
            for first in dp[j]:
                for second in dp[i-j]:
                    dp[i].add(first + second)
                    dp[i].add(first - second)
                    dp[i].add(second - first)
                    dp[i].add(first * second)
                    if second != 0 :
                        dp[i].add(first // second)
                    if first != 0 :
                        dp[i].add(second // first)
                    
        if number in dp[i]:
            return i
    return -1

풀이 출처) https://haesoo9410.tistory.com/270

<Level 3> N으로 표현 with 파이썬

---

와 진짜 어렵다.

 

문제 이해를 위한 자세한 설명: https://gurumee92.tistory.com/164

프로그래머스 문제 풀이 N으로 표현