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

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

프로그래머스

 

 

문제 해결 포인트

- 8번 이상 연산은 불가능하다는 것을 인지하고 각 인덱스 크기 만큼의 연산 수행시 결과 수들을 저장하는 배열 선언

     -  dp[i]에는 i는 i+1번 연산시 표현 가능한 수들이 들어간다.

- N이 5라면 55는 연산 2번을 의미하므로 해당하는 값을 미리 넣어 둔다.

 

- 4중 for문 

    1) 연산 횟수 i   

    2) 해당하는 연산 횟수 이하 수 j

    3) 연산을 위한 dp[j]의 모든 수 op1

    4) i가 될 수 있는 j의 짝궁 수 dp[i - j - 1]의 모든 수  op2

 

- 해당 피연산자 op1, op2의 모든 연산 후 원하는 값이 dp[i]에 들어있다면 최소 연산 수 이므로 반환

 

 

작성 코드

 

def solution(N, number):
    dp = [set() for i in range(8)]  # 연산 횟수 별 만들 수 있는 수 저장(최대 연산, 8)
    for i in range(1, 9):  # {N}, {NN}, {NNN} ...
        dp[i - 1].add(int(str(N) * i))

    for i in range(8):  # 1~8번의 연산 횟수 별 수행
        for j in range(i):  # 8번째 연산이라면 1~7
            for op1 in dp[j]:
                for op2 in dp[i - j - 1]:
                    dp[i].add(op1 + op2)
                    dp[i].add(op1 - op2)
                    dp[i].add(op1 * op2)
                    if op2 != 0:
                        dp[i].add(op1 // op2)
        if number in dp[i]:
            return i + 1
    return -1

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚