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

// 문제 요약

정수 N과 number 이 주어졌을 때

N과 4칙 연산 기호를 여러 번 사용하여서

number를 만들 수 있는 경우 중

N이 가장 적게 사용된 횟수를 구하여라

(단 8번 이상인 경우 -1을 return 해라)

 

// 사고

 

놀랍게도 태뷸레이션 문제다.

규칙을 발견하기 쉽지 않았는데

태뷸레이션으로 생각하지 않으면

다른 설명들도 이해하기 굉장히 난해하다.

(가지치기 처럼 생각하고 메모이제이션으로 볼 수도 있다.)

 

 

문제의 예시로 나왔던 5를 이용하는 경우를 보도록 하자.

 

N을 여러 번 사용하는 경우는 크게 두가지로 나눌 수 있는데

N을 그냥 여러 번 적어서 55나 555처럼 만드는 방법이고

연산기호를 넣어서 한번 더 적는 방법이다.

 

이때 N의 수를 1, 2, 3 이런 식으로 늘려가면서 경우의 수를 모두 찾아보면

위의 경우들처럼 수를 적을 수 있는데

* 기호는 연산자를 일반화해서 적은 것이고

왼쪽의 붉은 색 숫자는 연산자의 수

왼쪽의 민트 색 숫자는 조합이 만들어 지는 경우를 찾은 것이다.

 

민트색 수에 주목하면서 볼 필요가 있다.

N이 4번 사용되는 경우를 보면

N이 1번 사용된 경우와 3번 사용된 경우를 연산기호로 연결하여 만들 수 있고

N이 2번 사용된 경우와 2번 사용된 경우를 연산기호로 연결하여 만들 수 있고

N이 3번 사용된 경우와 1번 사용된 경우를 연산기호로 연결하여 만들 수 있다.

 

즉 'N이 사용된 횟수'에만 의존하여서 경우들을 모으고

그 경우에 해당하는 수들을 더해서 원하는 횟수가 된다면

그 조합들의 미리 계산된 경우를 조합하여 연산량을 줄일 수 있다는 이야기다.

 

여기서 중요한 부분은 나누기가 있기 때문에

일반화된 연산자는 교환법칙이 성립하지 않는다.

코드를 짤 때 주의해야한다.

 

// 풀이

 

def calculation(k_1,k_2):
    return (k_1 + k_2,
            k_1 - k_2,
            k_1 * k_2,
            k_1 / k_2 if k_2 > 0 else 0)

def solution(N, number):
    if N == number:
        return 1
    
    # table[number_of_N][number_of_calculation]
    num_of_N = [[0]]
    for i in range(1, 9):
        if i == 1:
            num_of_N.append([N])
            continue
        
        num_of_cal = set()
        for j in range(1, i):
            for k_1 in num_of_N[j]:
                for k_2 in num_of_N[i-j]:
                    for cal in calculation(k_1, k_2):
                        if cal == number:
                            return i
                        num_of_cal.add(cal)
        NNN = int(str(N)*i)
        if NNN == number:
            return i
        num_of_cal.add(NNN)
        num_of_N.append(num_of_cal)
    
    return -1

 

for문이 굉장히 여러번 겹쳐있어서 의아했을 것이다.

하지만 시간 이슈없이 모두 통과된다.

외냐하면 8이 넘어가는 경우는 모르겠으나

점진적으로 num_of_cal이 증가하기 때문에 8번까지는

시간복잡도에 큰 영향을 주지 않는다.

 

num_of_N은 N이 사용된 횟수를 나타내는 인덱스를 따르고

num_of_cal은 4칙연산이 적용된 수들의 인덱스를 따른다.

이렇게 작성된 테이블을 새로 업데이트할 때는

필요한 숫자가 미리 연산되어 있는 위치로 가서 불러와서 사용하면 된다.

 

중요한 부분은 N을 그냥 여러번 적은 경우도 반드시 검사해주고 넘어가야 틀리지 않는다.

 

어려운 문제였다.