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

문제

 

 

 

코드

def solution(N, number):
    if N == number:
        return 1
    
    answer = -1
    arr = [set() for _ in range(8)]
    
    for i in range(len(arr)):
        arr[i].add(int(str(N)*(i+1)))
    
    for i in range(1,8):
        for j in range(i):
            for op1 in arr[j]:
                for op2 in arr[i-j-1]:
                    arr[i].add(op1+op2)
                    arr[i].add(op1-op2)
                    arr[i].add(op1*op2)
                    if op2 != 0:
                        arr[i].add(op1//op2)
        if number in arr[i]:
            answer = i+1
            break
    
    return answer

 

 

풀이방법

이 문제는 동적 계획법을 사용하는 문제로 주어진 N을 가지고 사칙 연산만 사용하여 number를 만들 수 있는 최소 횟수를 구하는 문제입니다.

처음에 이 문제를 봤을 때 어떻게 동적계획법으로 문제를 풀어나가야 하는지 몰라서 헤매다가 유튜브 풀이법을 참고하여 풀이를 작성했습니다. 동적 계획법을 적응하려면 많은 문제를 풀어야 할 것 같네요.. 

 

우선 set() 자료구조를 사용해서 8개를 만들어 줍니다. 8개를 만드는 이유는 8개보다 크면 -1을 return 하는 조건 때문입니다.

set()을 만들고 set 자료구조에 주어진 N을 i+1갯수만큼 값을 넣어줍니다. 그러면 다음과 같이 set()에 값이 들어가게 됩니다.

 

그러고 나서 op1과 op2를 반복문을 통해서 사칙연산을 반복하게 되는데 이 과정이 동적계획법의 과정이라고 생각하면 될 것 같습니다.

i가 0부터 증가하면서 set자료구조 안에 경우의 수를 구해서 저장해 두고 i값이 커질수록 op1, op2를 불러와서 연산만 하는 것이기 때문에

동적계획법을 사용되었습니다. 그리고 만약 내가 원하는 결과 값 Number가 현재 구한 arr [i]에 존재하게 된다면 그 횟수가 최소 횟수가 되기 때문에 break를 통해서 값을 return 하면 원하는 결과를 얻을 수 있게 됩니다.

 

처음에는 어떻게 해야할지 접근방법에 대해서 고민을 많이 했지만 동적계획법을 사용하는 문제를 많이 풀어보지 못해서 부족하다는 것을 느끼고 유튜브를 보고 참고하여 접근하는 방법에 대해서 알 수 있게 되었습니다. 아래는 제가 참고한 유튜브 링크입니다.

 

 

 

#Reference

https://www.youtube.com/watch?v=ZsVVTEfZee8