[프로그래머스] 동적계획법(DP) 01. N으로 표현

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

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

 

문제설명

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

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

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

 

제한사항

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

 

입출력 예

 

입출력 예 설명

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

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

 

풀이

주어진 숫자 N을 1번 또는 8번 사용해서 원하는 숫자를 만드는 문제이다.
N이 5라고 할때,
1번 사용해서 만들 수 있는 숫자는 5 하나이다.
2번 사용해서 만들 수 있는 숫자는 5+5, 5-5, 5*5, 5/5, 55 이다.
3번 사용하는 경우는 5를 1번 사용하는 경우와 2번 사용하는 경우를 사칙연산 해서 얻을 수 있다.
4번 사용하는 경우는 5를 1번 사용하는 경우와 3번 사용하는 경우, 2번 사용하는 경우를 2번 사칙연산하면 얻을 수 있다.

즉, 전 단계에서 생성한

숫자를 이용해서 다음 숫자를 생성하는 것이다.

빼기의 경우 55 - 5(50)와 5 - 55(-50)를 모두 체크하고 나누기에서 0으로 나누지 않게 확인한다.
5, 55, 555, 5555 같은 연산은 단순 붙이는 연산이기 때문에 미리 입력해야한다.

if N == number :
        return 1
    
    total_set = [set() for _ in range(8)]
    
    for i in range(8):
        total_set[i].add(int(str(N)*(i+1)))

number와 n이 같은 경우에는 연산하지 않고 바로 답을 출력한다.

최대 8번까지 사용하기 때문에 8개의 set을 생성하였다. 
(중복되는 숫자가 발생하기 때문에 제거를 하기 쉽게 set으로 생성)

 

for i in range(8):
        #print(i)
        for j in range((i+1)//2):
            #print(f"{i-j-1} {j}")
            for op1 in total_set[i-j-1]:
                for op2 in total_set[j]:
                    total_set[i].add(op1+op2)
                    total_set[i].add(op1-op2)
                    total_set[i].add(op2-op1)
                    total_set[i].add(op1*op2)
                    if op2 != 0:
                        total_set[i].add(op1//op2)
                    if op1 != 0:
                        total_set[i].add(op2//op1)
                        

2번 사용은 1 + 1
3번 사용은 2 + 1
4번 사용은 3 + 1 , 2 + 2 .....

앞에 2번의 반복문을 이용해서 위의 숫자들을 만들어냈다.
그 후 이미 만들어져있는 set들을 연산하여 다음 set을 만들어냈다.

for i in range(8):
        if number in total_set[i]:
            return i+1
    

    
    return answer

가장 적은 횟수를 사용해서 만들어야하기 때문에 0번부터 7번까지 확인한다.

 

 

전체 코드

def solution(N, number):
    answer = -1
    
    if N == number :
        return 1
    
    total_set = [set() for _ in range(8)]
    
    for i in range(8):
        total_set[i].add(int(str(N)*(i+1)))
           

        
    for i in range(8):
        #print(i)
        for j in range((i+1)//2):
            #print(f"{i-j-1} {j}")
            for op1 in total_set[i-j-1]:
                for op2 in total_set[j]:
                    total_set[i].add(op1+op2)
                    total_set[i].add(op1-op2)
                    total_set[i].add(op2-op1)
                    total_set[i].add(op1*op2)
                    if op2 != 0:
                        total_set[i].add(op1//op2)
                    if op1 != 0:
                        total_set[i].add(op2//op1)
                        
    for i in range(8):
        if number in total_set[i]:
            return i+1
    

    
    return answer