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

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

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

 

 

< 문제 설명 >

number와 N이 주어진다.

숫자 N과 사칙연산을 통해 number를 표현할 수 있다.

아래는 5를 이용해 12를 나타낸 예시이다.

이렇게 number와 N이 주어지면 N이 사용된 가장 적은 횟수를 리턴하면 된다.

만약 8회 이상이라면 -1을 리턴한다.

 

 

< 문제 이해 > 

N이 5번 사용된 것은 N이 1번 사용된 것과 N이 4번 사용된 경우의 사칙연산으로 이루어질 수도있고

2번, 3번 사용된 경우의 사칙연산으로 이루어질 수 있다.

따라서 dp 문제다!!!!

그리고 사칙연산은 연산자에 따라 앞뒤로 어떤 수가 오는지가 중요하니까

3번, 2번 사용된 경우와 4번, 1번 사용된 경우도 다 따져주어야한다.

 

 

 

< 문제 풀이 >

def solution(N, number):
    dp = [[] for i in range(9)]			# 9개의 리스트 생성. 0번째 리스트는 사용X
        
    for i in range(1,9):			# N이 i번 쓰인경우
        dp[i].append(int(str(N)*(i)))		# 사칙연산이 이루어지지 않는 수 삽입. 예)5,55,555
        
        for j in range(1,i):			
            for x in dp[j]:			# N이 j번 쓰인 경우의 수와
                for y in dp[i-j]:		# N이 i-j번 쓰인 경우의 사칙연산
                    dp[i].append(x+y)
                    dp[i].append(x-y)
                    dp[i].append(x*y)
                    if y != 0 :
                        dp[i].append(x//y)
            
        if number in dp[i] : return i		# i번째 쓰인경우에 number가 있으면 i리턴
       
    return -1					# 8개의 리스트 안에 number없으면 -1리턴