[문제 풀이] N으로 표현

코딩테스트 연습 - N으로 표현

 

해결 과정

처음 DP인거 무시하고 풀었는데 모든 테케 통과 못함. 해설 보고 IDEA 얻은 뒤에 다시 풀어서 모든 테케 통과. DP의 IDEA를 생각할 수 있어야 풀리는 문제였다.

 

나의 풀이

from collections import defaultdict
def calculate(arr1, arr2, operator):
    temp = []
    for i in arr1:
        for j in arr2:
            try:
                temp.append(int(eval(str(i) + operator + str(j))))
            except:
                pass

    return temp

def solution(N, number):
    answer = -1
    
    # DP 저장소
    DP = defaultdict(list)
    
    for i in range(1, 9):
        numbers = []
        
        # numbers 채우기
        numbers.append(int(str(N)*i))
        for j in range(1, i):
            numbers += calculate(DP[j], DP[i-j], "+")
            numbers += calculate(DP[j], DP[i-j], "-")
            numbers += calculate(DP[j], DP[i-j], "*")
            numbers += calculate(DP[j], DP[i-j], "//")
        
        numbers = list(set(numbers))
        
        if number in numbers:
            return i
        else:
            DP[i] = numbers
            
    return answer

 

다른 풀이

대부분 다음 풀이처럼 set과 4중 for문을 사용하는 경우가 많았다.

def solution(N, number):
    answer = -1 #답이 없을때
    dp = []
    for i in range(1, 9): #return 최대값 8
        rs = set() #연산 결과 저장
        iter_number = int(str(N) * i) #연속숫자
        rs.add(iter_number)
        for j in range(0, i-1):
            for op1 in dp[j]:
                for op2 in dp[-j-1]: #op1과 op2의 N갯수 합이 i개, 사칙연산
                    rs.add(op1 - op2)
                    rs.add(op1 + op2)
                    rs.add(op1 * op2)
                    if op2 != 0:
                        rs.add(op1 // op2)
        if number in rs:
            return i
        dp.append(rs)
    return answer

효율성 측면에서 이게 더 나은거 같기도 하다.

 

IDEA

Dynamic Programming

드디어 첫 DP 문제를 개시했다. DP는 동적 계획법이라고도 불리는데, 동적 할당에 쓰이는 동적 의미와는 다르다. 

예시로, 피보나치 수열을 더 효율적으로 계산하는 방법을 생각해보면 된다. 다른 대표적인 예시로는 Knapsack Problem이 있다.

f(n) = f(n-1) + f(n-2) 라고 했을 때, 

f(0) = 0, f(1) = 1

f(2) = f(1) + f(0)

f(3) = f(2) + f(1) 

f(3)을 구할 때, 미리 구해 둔 f(2)를 활용하여 계산하면 불필요한 반복이 없어진다.

 

이 문제에서는 DP 아이디어를 떠오르면 코드가 간결해지는 문제이기도 했다. 사칙연산과 () 괄호 사용이 자유자재여서 케이스가 정말 많아보이지만, 아래에서 부터 차근차근 생각해보면 DP로 효율적으로 계산할 수 있다.

 

 

eval에서 Syntax 오류가 날 때 처리하는 방법

try:
    eval("1 + 2) + 3")
except:
    pass

 

python의 mutable VS immutable

mutable 타입: list, set, dictionary

immutable 타입: int, float, bool, string, tuple

s = [set()] * 9 # 같습니다.
s = [set() for x in range(9)] # 다릅니다.

if s[1] is s[2]:
    print("같습니다.")
else:
    print("다릅니다.")