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

프로그래머스 <N으로 표현>

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

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

---

<N으로 표현>

주어진 N과 number가 있을 때,

N으로 이루어진 숫자들을 사칙연산으로 number를 만들 때 N이 최소 몇 개 필요한지 구하여라.

이때 8보다 크다면 -1을 출력하여라.

---

문제 해결

이 문제는 DP 문제이다.

처음에 8보다 클 때 -1을 출력하라는 조건을 못보고 각 숫자들을 만들 때 필요한 최소 값을 구하려고 했다.

그런데 이렇게 풀 방법이 너무너무 별로라서 뭔가 했는데 이렇게 푸는게 아니었다.

 

N을 1개부터 8개 이용하여 각각 어떤 숫자들을 만들 수 있는지 구하는 문제이다.

 

1) N과의 사칙연산

일단 N을 1개 이용해서 만들 수 있는 숫자는 N 하나 이다.

그리고 N을 2개 이용해서 만들 수 있는 숫자는 NN과 N을 1개 이용해서 만든 숫자를 N과 사칙연산하면 된다.

N을 3개 이용해서 만들 수 있는 숫자는 NNN과 N을 2개 이용해서 만든 숫자들을 N과 사칙연산하면 된다.

이런 식으로 N을 1개부터 8개까지 이용하여 각각 어떤 숫자들을 만들 수 있는지 구할 수 있다.

 

즉 'N을 i개 이용해서 만들 수 있는 숫자 = N을 i-1개 이용해서 만들 수 있는 숫자와 N과의 사칙연산으로 만들어지는 숫자' 이다.

 

그리고 또 숫자를 만들 수 있는 방법이 있다.

 

2) 만들어진 숫자를 이용해 사칙연산

N을 1개 이용해서 만들 수 있는 숫자와 N을 1개 이용해서 만들 수 있는 숫자를 사칙연산하면 N을 2개 이용해서 만들 수 있는 숫자를 구할 수 있다.

N은 2개 이용해서 만들 수 있는 숫자와 N을 1개 이용해서 만들 수 있는 숫자를 사칙연산하면 N을 3개 이용해서 만들 수 있는 숫자를 구할 수 있다.

 

1) 방법과 2) 방법을 모두 합쳐서 N을 n개 이용해서 만든 숫자들을 구할 수 있다.

 

for문을 2부터 8까지 돌려서 N을 2개부터 8개까지 이용해서 만들 수 있는 숫자들을 구한다. 

이때 number가 만들어졌으면 그때의 for문 파라미터 값을 반환하면 된다. 

---

코드

def solution(N, number):
    if N == number:
        return 1
    answer = operate(N, number)
    return answer

def operate(N, number):
    total = []
    count = [[] for _ in range(9)]
    chk = [[], [], [1, 1], [1, 2], [1, 3, 2,2], [1, 4, 2,3],[1, 5, 2,4,3,3], [1, 6,2,5,3, 4], [1,7,2,6,3,5,4,4]]
    
    total.append(N)
    count[1].append(N)
    
    for use in range(2, 9):
        temp = N
        for i in range(1, use):
            temp += (10**i)*N
        if temp == number:
            return use
        count[use].append(temp)
        total.append(temp)
        for pn in count[use-1]:
            pnList = []
            pnList.append(pn-N)
            pnList.append(pn+N)
            pnList.append(pn*N)
            pnList.append(pn//N)
            
            for i in range(4):
                if pnList[i] == number: 
                    return use
                if pnList[i] > 0 and pnList[i] <= 32000 and (pnList[i] not in total):
                    count[use].append(pnList[i])
                    total.append(pnList[i])
        length = len(chk[use])
        if length > 0:
            for i in range(0, length, 2):
                for j in count[chk[use][i]]:
                    for k in count[chk[use][i+1]]:
                        chkList = []
                        chkList.append(k+j)
                        chkList.append(k-j)
                        chkList.append(j-k)
                        chkList.append(k*j)
                        chkList.append(k//j)
                        chkList.append(j//k)
                        for p in range(6):
                            if chkList[p] == number:
                                return use
                            if chkList[p] > 0 and chkList[p] <= 32000 and (chkList[p] not in total):
                                count[use].append(chkList[p])
                                total.append(chkList[p])
    return -1

 

풀다가 8보다 크다면을 8도 아니어야 된다고 생각해서 틀렸다!

---

결과

---