프로그래머스_N으로 표현

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

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

 

 

• 접근법

숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 구하는 문제이다. 즉 5를 이용해 10을 구하는 최소의 5 사용법은 (5+5) : 2개,  60을 구하는 방법은 (55 + 5) : 3개 이다.

N이 필요한 최소 개수가 9 이상이라면 -1을 return하므로 8개 까지 필요한 경우만 생각하면 된다.

 

내가 생각한 문제 접근법을 설명하면

*N이 n개 사용될 때 구할 수 있는 값들의 종류

- N이 1개일 때 경우의 수  +,-,*,/  N이 n-1개일 때 경우의 수

- N이 2개일 때 경우의 수  +,-,*,/  N이 n-2개일 때 경우의 수

.

.

.

- N이 n/2개일 때 경우의 수  +,-,*,/  N이 n-(n/2)개일 때 경우의 수

 

위의 n을 좀 더 간단화하여 표현하자면n = 3-> 3 = 2 + 1n = 4-> 4 = (1+3), (2+2)n = 5-> 5 = (1+4), (2+3)

 

즉 n이 1일때부터 8일때까지 모든 경우의 수를 사전에 미리 구했던 경우의 수를 참고하여 구한다.

 

 

• 코드 설명

from collections import defaultdict

def solution(N, number):
    if N == number : return 1;
    n_lst = defaultdict(set)
    n_lst[1].add(N)
    
    for n_num in range(2, 9) :
        n_lst[n_num].add(int(str(N) * n_num))
        for i in range(1, n_num//2 + 1) :
            for i_num in n_lst[i] :
                for j_num in n_lst[n_num-i] :
                    n_lst[n_num].add(i_num + j_num)
                    n_lst[n_num].add(i_num - j_num)
                    n_lst[n_num].add(j_num - i_num)
                    n_lst[n_num].add(i_num * j_num)
                    
                    if j_num !=0 : n_lst[n_num].add(i_num // j_num);
                    if i_num != 0 : n_lst[n_num].add(j_num // i_num);

                    if number in n_lst[n_num] :
                        return n_num
    return -1

- 사용한 알고리즘 : DP(Dynamic Programming)

- defaultdict(n_list) 를 이용하여 n이 1~8일때 나올 수 있는 값들을 저장한다.

- n이 1일때는 경우의 수가 한가지(N)이므로 n_lst[1]에 미리 N을 저장해 둔다

- 첫번째 for문은 n이 2 ~ 8일때를 의미한다

- 두번쨰 for문은 n가지의 경우의 수가 참조할 그 전에 구한 m가지 경우의 수/2를 의미한다

    -> 절반만 for문을 처리한 이유는 나머지 절반의 값은 n에서 뺀 값으로 계산이 가능하다

- 3번째 for문(i_num)은 i가지를 사용했을 때 나오는 값들을 참조한다

- 4번째 for문(j_num)은 n-i가지를 사용했을 때 나오는 값들을 참조한다

- 종속문장은 i가지, n-i가지 경우의 값들을 서로 사칙연산하여 set리스트에 추가하는 것이다

- 종속문장에서 if문은 나눌 때 몫이 0일때를 제외처리 한것이다

- 빼기 연산, 나누기 연산이 2개인 이유는 빼기와 나누기는 숫자가 앞뒤로 바뀜에 따라 결과값도 달라지기 때문이다

- 이렇게 구한 값들중에 구하고자하는 number가 있는지 if문을 통해 확인하고 있다면 return, 끝까지 돌려도 구해지지 않는다면 -1을 return 한다