프로그래머스 - N으로 표현

문제 설명

N과 number가 주어졌을 때, N과 사칙연산을 사용하여 number를 만들 수 있는 경우의 수 중, 가장 작은 수를 출력하는 문제이며, N이 8개 이상 사용된 경우 -1을 출력한다.

접근 방법

dp문제 임을 알고 있었지만, 스스로 생각해내기 어려운 문제였다.

N의 11배, 111배, 1111배 이런 식으로 생각하다가, 나누어 떨어지는 경우를 생각하다가.. 실패했다.

접근 방법은 다음과 같다.

• N이 8개 이상 사용되면 안되기 때문에, N이 1개 일 때부터 8개일 때 까지의 경우를 고려
  
  
• 중복을 허용하지 않는 set()을 활용해 N이 1개일 때 사칙연산, 2개일 때 사칙연산을
  N개 까지 진행
  
  
• 결국 dp가 [{5}, {55, 0(5-5), 1(5//5), 10(5+5), 25(5*5)}, {555, 2(10//5), 60(55+5), ...] 같이 모든 경우의 수를 고려
  
  
• 생성된 값들 중 number가 도출된다면 N의 개수를 나타내는 i를 정답으로 출력
  for문으로 수행하여, 도출되자마자 출력하면 자연스럽게 최소값 도출

작성 코드

def solution(N, number):
    answer = -1		# 기본값 -1 할당
    dp = []			# dp 배열 선언
        
    for i in range(1, 9):	# N이 1부터 8까지
        value_arr = set()   # set으로 중복 값 삭제
        
        value_arr.add(int(str(N) * i)) 	# N이 i개인 경우 추가
        
        for j in range(0, i-1):			
            for op1 in dp[j]:			# 사칙연산 과정 수행
                for op2 in dp[-j-1]:	# 1-5, 5-1은 다른 결과이므로
                    value_arr.add(op1 + op2)
                    value_arr.add(op1 - op2)
                    value_arr.add(op1 * op2)
                    if op2 != 0:
                        value_arr.add(op1//op2)    

        if number in value_arr:		# 사칙연산을 수행했을 때, number가 있다면
            answer = i				# 사용된 N의 개수를 정답에 넣고 종료
            break						
            
        dp.append(value_arr)
    return answer