[알고리즘/DP] 프로그래머스 N으로 표현하기

8. 프로그래머스 N으로 표현하기

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

 

문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)12 = 55 / 5 + 5 / 512 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

N number return

5	12	4
2	11	3

 

입출력 예 설명

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

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

 

 

---

💡나의 문제 풀이

문제 해결 아이디어

• N으로 표현할 수 있는 수는 우선, N을 이어붙인 수이다. (5, 55, 555 , )
  • N에 대한 사칙 연산으로 표현할 수 있다. (+, -, * , / ) → 이때 - 와 / 는 앞 뒤 숫자의 순서에 따라 그 값이 달라진다.
• dp 테이블에 각각 N을 1, 2, 3 ,… 번 사용한 결과들에 대한 리스트를 append한다.

 

고려 사항

• dp 테이블에 저장된 값을 이용하여 N에 대한 사칙연산을 한 결과값을 고려한다.
  • 예를 들어, dp[4] (N을 4번 사용하여 표현한 수는) 1번 사용한 결과 값과 3번 사용한 결과값의 사칙연산, 2번 사용한 결과 값과 2번 사용한 결과 값에 대한 사칙 연산으로 표현할 수 있다.
• 중복되는 값이 많아질 수 있기 때문에 set 집합 자료형을 이용한다.

 

작성 코드

• 처음 작성한 코드는 다음과 같다.
• N을 사용한 횟수와 사칙연산의 조합으로 만들 수 있는 수들을 담는 DP 테이블 dp를 만든다.
• 1번~8번까지 돌며, N을 i 번 이어붙인 수를 먼저 append 하고, i-1번 사용하여 만든 수들이 담긴 dp[i-1] 리스트의 값들과 N을 사칙 연산한 결과 값들을 arr에 저장하여, 중복되는 수가 없고 (→ set 으로 변경하여 손쉽게 해결) 해당 값이 1 이상, 32000 이하인 경우 dp[i] 리스트에 새로 append 한다.
• 찾고자 하는 수 number에 dp[i]에 있는 경우 사용 횟수를 뜻하는 i 를 리턴한다.
• 8번을 사용했는데도 리스트에 담겨져 있지 않다면, -1 를 리턴한다.

def solution(N, number):
    dp = [[] for _ in range(9)] # N 사용 횟수에 대한 DP테이블
 
    
    for i in range(1, 9):
        # i : number 사용 횟수
        dp[i].append(int(str(N)*i)) # 5, 55, 555, ... (N을 이어붙인 수)

        # dp[i-1]과 dp[i]에 대한 연산
        for j in dp[i-1]:
            arr = [j+N, j*N, j//N, N//j, j-N, N-j]
            for a in arr:
                if a not in dp[i-1] and a>=1 and a<=32000:
                    dp[i].append(a)

        if number in dp[i]:
            return i

    return -1

 

---

수정 코드 1

• 위의 코드에서 놓친 것은, 이전 리스트에 담긴 것들에 N에 대한 사칙 연산을 한 번 더 추가하는 것만으로는 안된다는 것이다.
  • 예를 들어 N을 4번 조합하여 만든 숫자에 대해, dp[3]의 값들에 N을 사칙 연산한 값 뿐만 아니라, dp[2]와 dp[2]의 조합이다.

def solution(N, number):
    dp = [[] for _ in range(9)] # N 사용 횟수에 대한 DP테이블

    for i in range(1, 9):
        # i : number 사용 횟수
        dp[i].append(int(str(N)*i)) # 5, 55, 555, (N을 이어붙인 수)
     
        # dp[j]과 dp[i-j]에 대한 연산
        for j in range(1,i//2+1):
            for k in dp[j]:
                for m in dp[i-j]:
                    arr = set()
                    arr = [k+m, k*m, k//m, m//k, k-m, m-k]
                    
                    for a in arr:
                        if a>=1 and a<=32000 and a not in dp[i]:
                            dp[i].append(a)

        if number in dp[i]:
            return i 
    return -1

 

---

수정 코드2

• 답안 풀이들을 보고 난 후, 다시 복기하며 작성해보았는데 테스트 케이스 9번이 풀리지 않았다. 문제는 i에 대해 바깥 for문이 돌 때, 1부터 시작했다는 점. N==number인 경우에는 return i 가 작동하지 않아 테스트 9번이 통과하지 못했던 것.
• 결국 반복문 돌기 전에 N==number 인 경우는 1을 리턴하도록 수정

def solution(N, number):
    dp = [{N}]  # dp 리스트 (먼저 N을 삽입)
    if N==number:
      return 1
      
    for i in range(1,9):
        # i : number 사용 횟수
        arr = [int(str(N)*(i+1))] # 5, 55, 555, (N을 이어붙인 수)
        # dp[j]과 dp[i-j]에 대한 연산
        for j in range(0, i//2+1):
            for k in dp[j]:
                for m in dp[i-j-1]:
                    arr.append(k+m)
                    arr.append(k-m)
                    arr.append(m-k)
                    arr.append(k*m)
                    if m!=0:
                        arr.append(k//m)
                    if k!=0:
                        arr.append(m//k)
        dp.append(set(arr))
        if number in set(arr):
            return i+1
        
    return -1

print(solution(5,12))
print(solution(2,11))

 

---

답안 코드

def solution(N, number):
    S = [{N}]
    for i in range(2, 9):
        lst = [int(str(N)*i)]
        for j in range(0, int(i / 2)):
            for x in S[j]:
                for y in S[i - j - 2]:
                    lst.append(x + y)
                    lst.append(x - y)
                    lst.append(y - x)
                    lst.append(x * y)
                    if x != 0: lst.append(y // x)
                    if y != 0: lst.append(x // y)
        if number in set(lst):
            return i
        S.append(lst)
    return -1

 

리뷰 및 점검

• 처음에 문제 해결 아이디어를 얻긴 했지만, 이전의 dp테이블을 조합하는 어려움이 있었고, 이후에도 효율적이지 않은 방법으로 코드를 작성했다.
• set() 집합 자료형을 잊지 말자!