(프로그래머스) N으로 표현

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

 

 

dp[0] = N을 0번 사용해서 만들 수 있는 숫자들의 그룹

dp[1] = N을 1번 사용해서 만들 수 있는 숫자들의 그룹

dp[2] = N을 2번 사용해서 만들 수 있는 숫자들의 그룹

 

dp[3] = N을 3번 사용해서 만들 수 있는 숫자들의 그룹

        = [NNN] + dp[1]에 있는 모든 숫자들과 dp[2]에 있는 모든 숫자들을 +, -, *, / 해서 만들 수 있는 숫자들의 그룹

 

점화식:

dp(n) = [dp(i)의 모든 숫자들 + - * ÷ dp(n-i)의 모든 숫자들] (i = 1부터 n-1)

(점화식에서 55 555 5555 등의 숫자는 제외했다. 이러한 숫자들은 n마다 하나씩 있다. N을 n번 써준 숫자.)

 

문제에서 괄호까지 넣을 수 있다고 해서 헷갈렸다.

예를 들어 5를 3개 가지고 만들 수 있는 연산식 중 5 + 5 ÷ 5 가 있을 때,

(5 + 5) ÷ 5 와 5 + (5 ÷ 5)는 다른데 이걸 어떻게 고려해줘야 하나? 싶을 수도 있을 것이다.

하지만 다시 생각해보면 (5 + 5)와 (5 ÷ 5)는 5를 2개 가지고 만든 연산식이다. 

즉 저 식들을 일반화해서 생각해보면

[5를 2개 가지고 만들 수 있는 수] + - * ÷ [5를 1개 가지고 만들 수 있는 수]

[5를 1개 가지고 만들 수 있는 수] + - * ÷ [5를 2개 가지고 만들 수 있는 수]

가 되는 것이다. 그냥 두 번 쓴 게 아니다. -, ÷일 때는 식의 순서가 달라지면 결과도 달라질 수 있다.

 

j의 range를 (1, i // 2 + 1)로 잡은 이유는 

우선 dp[0]은 0이므로 볼 필요가 없다. dp[n] = dp[0] + - * ÷ dp[n]도 맞긴 한데, 어차피 다 중복되는 숫자들이라 해줄 필요가 없다.

range의 두번째 인자가 i // 2 + 1 라는 것은 j를 i // 2 까지 보겠다는 건데, 그 이유는 어차피 중복되기 때문이다.

예를 들어 dp(4) = dp(1) + - * ÷ dp(3), dp(2) + - * ÷ dp(2), dp(3) + - * ÷ dp(1) 인데 기울임 처리한 마지막 연산은 밑줄 친 첫번째 연산과 앞 뒤를 바꿔준 것 밖에는 다르지 않다. +와 *는 앞뒤가 바뀌어도 결과가 같기 때문에 신경 안 써도 되고, -와 ÷만 앞뒤로 바꿔서 해주면 된다.

 

i, j, k, m 등 요상한 변수가 많아서 헷갈릴 수 있는데 변수에 별다른 뜻이 없어서 어쩔 수가 없었다...

i = 2 부터 해서 직접 변수 안에 무엇이 들어가나 써보면 좀 이해하기 쉬울 것이다.

 

# Lvl3. N으로 표현


def solution(N, number):
    answer = 0
    dp = [0, {N}]  # N을 0번, 1번 가지고 만들 수 있는 수들의 집합
    
    if N == number:
    	return 1
        
    for i in range(2, 9):  # N을 2번 ~ 8번을 가지고 만들 수 있는 수들의 집합 구하기
        case = {int(str(N)*i)}  # N, NN, NNN ...
        for j in range(1, i // 2 + 1):  # dp(3) = [dp(1) +-*/ dp(2)] 여기서 j=1, i-j=2
            for k in dp[j]:
                for m in dp[i-j]:
                    case.add(k + m)
                    case.add(k * m)
                    
                    # j는 i의 절반까지만 구하고 연산할 때 앞뒤를 바꿔줌
                    case.add(k - m)
                    case.add(m - k)
                    if k > 0:
                        case.add(m // k)
                    if m > 0:
                        case.add(k // m)

        if number in case:
            #print(dp)
            return i
        else:
            dp.append(case)

    return -1