[프로그래머스 level3 N으로 표현] 문제를 넓게 바라보기

해결해야하는 문제는 다음과 같다.

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

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

 

 

 

처음에는 너무 단순하게 접근하였다가 5,6,7,8번에서 실패가 떴다.

dynamic programming을 위한 table을 생성하고 

N의 개수가 1개일 때 가능한 연산 결과를 -> dp[1]에 저장하고,

N의 개수가 2개일 때 가능한 연산 결과를 -> dp[1] 내용을 바탕으로 dp[2]에 저장하고,

N의 개수가 3개일 때 가능한 연산 결과를 -> dp[2] 내용을 바탕으로 dp[3]에 저장하는 방식을 사용하였다.

그리고 찾고자하는 number가 현재 dp table 순서에 있다면 현재 몇개를 가지고 만들었는지를 return 해주도록 작성하였다.

이러한 아이디어로 작성한 코드는 다음과 같다.

def solution(N, number):
    if N == number:
        return 1
    
    dp = [set() for i in range(9)]
    dp[1].add(N)
    
    for i in range(2,9):
    	temp=int(str(N)*i)
        dp[i].add(temp) 
        for j in dp[i-1]:
            dp[i].add(j-N)
            dp[i].add(N-j)
            dp[i].add(N+j)
            dp[i].add(j//N)
            dp[i].add(j*N)

            if j > 0:
                dp[i].add(N//j)  
        
        if number in dp[i]:
            return i
    
    return -1

 

하지만 이렇게 작성하게 되는 경우, 다음과 같은 문제를 갖게 된다.

4개의 5를 활용하여 나올 수 있는 사칙 연산 결과를 담는다고 생각해보자.

(5,5,5,5) -> (5)와 (5,5,5)의 연산, (5,5)와 (5,5)의 연산, (5,5,5)와 (5)의 연산(중복)

이러한 연산에 대해 모든 결과를 포함할 수 없다.

현재의 코드에서는 5를 4개 사용하는 연산(i=4)에서,

5555라는 숫자 추가와, 이전 (5,5,5)의 연산 중 (5)를 활용한 연산만 dp[4]에 저장하게 된다.

 

 

따라서 이러한 문제점을 극복하기 위해서 

(5,5,5,5) -> (5)와 (5,5,5)의 연산, (5,5)와 (5,5)의 연산, (5,5,5)와 (5)의 연산(중복)

를 유의하며 이를 포함할 수 있는 방법에 대해서 생각해보았다.

괄호 및 사칙연산이 모두 가능하기 위해서는 dp[i]를 고려할 때, dp[cnt]와 dp[i-cnt] 숫자의 연산을 수행하면 된다.

dp[i]에는 i개의 N이 들어가는 연산을 수행해야 하므로, cnt + (i-cnt) = i 임을 활용하여 

dp[cnt] , dp[i-cnt]의 숫자의 연산을 수행한다는 뜻이다!

 

 

따라서 이러한 아이디어로 작성한 코드는 다음과 같다.

def solution(N, number):
    if N == number:
        return 1
    
    dp = [set() for i in range(9)]
    dp[1].add(N)
    
    for i in range(2,9):
        temp=int(str(N)*i)
        dp[i].add(temp)  
        for cnt in range(1,i):
            for a in dp[cnt]:
                for b in dp[i-cnt]:
                    dp[i].add(a-b)
                    dp[i].add(b-a)
                    dp[i].add(a+b)
                    dp[i].add(a*b)

                if a!=0:
                    dp[i].add(b//a)
                if b!=0 :
                    dp[i].add(a//b)
            
        
        if number in dp[i]:
            return i
    
    return -1

 

 

이 문제는 생각하는데 굉장히 오랜 시간이 걸렸던 것 같다. 다이나믹 프로그래밍과 최단 경로 찾는 문제만 나오면 쫄게되는데,, 이러한 부분을 보완할 수 있도록 더 생각하는 힘을 길러야 겠다 ㅜㅜ