프로그래머스 - N으로 표현

문제 설명

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

입출력 예Nnumberreturn

5	12	4
2	11	3

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다

 

 

풀이

def solution(N, number):
    
    # example N=5, number = 12, return 4
        
    if N==number or N==0:                       # corner case, N==number 일 경우, N이 0일때 나눗셈 하는 경우 방지
        return 1
        
    d = [[] for _ in range(10)]                 # 얕은 복사 안되도록, N 최대값만큼 생성. d = [] * 10 으로 생성하면 같은 주소값 가르켜서 안됨.
    d[0] = [N]                                  # 1개만 사용할 경우
    d[1] = [N*11, N+N, N-N, N//N, N*N]          # 2개 사용할 경우
    
    if number in d[1]:                          # d[1]이 답일 경우 special case
        return 2
    
    for i in range(2,8):                        # 문제에서 return값 최대를 8까지로 명시했으므로 8까지 반복.
        num=N
        temp=i
        while temp>0:
            num+= 10**temp*N                    # 555, 5555 등의 연속된 수 num 만들기
            temp-=1
        d[i].append(num)                        # 555, 5555 추가

        for l in range(i):
            for j in range(len(d[l])):
                for k in range(len(d[i-l-1])):
                    if d[l][j] + d[i-l-1][k] not in d[i]:           # d(4) = d(3)+d(1) , d(2)+d(2) 모든 경우의수
                        d[i].append(d[l][j] + d[i-l-1][k])          
                    if d[l][j] * d[i-l-1][k] not in d[i]:
                        d[i].append(d[l][j] * d[i-l-1][k])          # d(4) = d(3)*d(1), d(2)*d(2)
                    if d[l][j] - d[i-l-1][k] not in d[i]:
                        d[i].append(d[l][j] - d[i-l-1][k])          # 빼기, 나누기는 d(3)-d(1)과 d(1)-d(3)이 다른 값이기 때문에 순서 바꿔서 계산해줘야함
                    if d[i-l-1][k] - d[l][j] not in d[i]:           # ex) 55-5 != 5-55
                        d[i].append(d[i-l-1][k] - d[l][j])
                    if d[i-l-1][k] != 0:
                        if d[l][j] // d[i-l-1][k] not in d[i]:
                            d[i].append(d[l][j] // d[i-l-1][k])
                    if d[l][j] != 0:
                        if d[i-l-1][k] // d[l][j] not in d[i]:
                            d[i].append(d[i-l-1][k] // d[l][j])
        if number in d[i]:
            return i+1

                    
    return -1

 

 

TIL

다이나믹 프로그래밍은 큰 문제를 어떻게 작게 쪼갤지를 결정해야함. 이 문제는 "최솟값이 8보다 크면 -1을 return 합니다."라는 조건이 있기 때문에 가장 작은 조각부터 쌓아올라가는 Bottom-up 방식으로 풀었다. 아마 9를 넘어가면 실행시간이 기하급수적으로 커져서 일부러 상한선을 정해준 듯 하다.

d(N) = d(1) + d(N-1) , d(2) + d(N-2) ...

이런 식으로 사칙 연산에 대해서 모든 결과값의 조합을 계산해야 한다. 특히 빼기나 나눗셈 연산은 앞 뒤 순서가 바뀌면 결과값도 완전히 다르게 나오기 때문에 순서도 바꿔서 계산해 줘야 한다. 

 

 

그리고 파이썬의 얕은 복사에 대해서 몰라서 배열 선언하는 부분에서 애를 먹었다. 

 

잘못된 방법

d= [] * 3

print(d) # [[],[],[]]

d[0].append(1)

print(d) # 예상값 == [[1],[],[]]   출력 값 == [[1],[1],[1]]

Python에서 * 연산자를 이용해서 배열을 선언하게 되면 얕은 복사(Shallow copy)가 된다. 즉 배열 내의 요소들이 같은 객체를 가리킨다. 따라서 이 방식으로 2차원 배열을 선언하고 요소에 접근하면 다른 요소들의 값도 같이 바뀐다.

 

 

올바른 방법

d = [[] for _ in range(3)]  

d[0].append(1)

print(d) # [[1],[],[]] expected value