Hama Develop

프로그래머스-N으로 표현, 파이썬

February 21, 2020

출처

문제 설명

아래와 같이 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 합니다.

입출력 예

N number return
5 12 4
2 11 3

풀이

아이디어는 간단하다.

  1. 주어진 숫자 N으로 각 횟수당 만들수 있는 숫자 조합을 만든다.
  2. 만들어진 숫자 조합에 number로 주어진 숫자가 있는지 확인한다.
  3. 만약 있다면 그 시점에서의 횟수를 답으로 리턴한다.
  4. 없다면 횟수를 하나 늘리고 가능한 숫자 조합을 만들고 1~3을 반복한다.

하지만, 이를 어떻게 구현해 낼지가 난제였다.

먼저 N 과 사칙연산을 통해 만들어 낼 수 있는 숫자가 어떤게 있는지 알아야 한다.

이를 이해하기 위해 작은 숫자의 예시를 들어서 알아보자

N이 1일때 숫자 5로 만들수 있는 수


5


5, 딱 1개 뿐이다. 여기서 더하고 빼고를 할 수 없다.

N이 2일때 숫자 5로 만들수 있는 수


55(5를 2번 이어 붙임)

10(5+5), 25(5*5), 1(5/5), 0(5-5)


이처럼 5를 이어 붙여서 만드는 경우와 5를 사칙연산 해서 붙이는 경우가 생긴다.

N이 3일때 숫자 5로 만들수 있는 수


555(5를 3번 이어붙임)

15((5+5)+5), 5((5+5)-5), 2((5+5)/5), 50((5+5)*5)

30((55)+5), 20((55)-5)), 5((55)/5), 125((55)*5)


페턴이 보이는가?

5를 이어 붙여 만든 조합을 제외하고 생각해 보면,

N이 2인 숫자 조합을 만들기 위해서는 N이 1일때 경우의 수와 N이 1일때 경우의 수를 각각 사칙연산했다.

N이 3인 숫자 조합을 만들기 위해서는 N이 1일때 경우의 수와 N이 2일때 경우의 수를 각각 사칙연산했다.

즉, 특정 숫자만큼 5를 사용한 조합을 만들고 싶다면, 해당 숫자를 만들수 있는 덧셈 조합의 경우의 수 끼리 사칙연산을 해 주면 되는 것이다.

복잡하긴 하지만, N의 최대 수가 8이기 때문에 그리 많은 연산을 하지는 않을 것으로 보고 문제를 푼다.

def solution(N, number):
    possible_set = [0,[N]] # 조합으로 나올수 있는 가능한 숫자들, 여기에 계속 append하며 이후에 사용함
    if N == number: #주어진 숫자와 사용해야 하는 숫자가 같은 경우는 1개면 족하므로 1으로 놓는다. 
        return 1
    for i in range(2, 9): # 2부터 8까지로 횟수를 늘려 간다. 
        case_set = [] # 임시로 사용할 케이스 셋, 각 I 별로 셋을 만들어 possible set에 붙인다.
        basic_num = int(str(N)*i) # 같은 숫자 반복되는 거 하나를 추가한다.
        case_set.append(basic_num)
        for i_half in range(1, i//2+1): # 사용되는 숫자의 횟수를 구해야 하는데, 절반 이상으로 넘어가면 같은 결과만 나올 뿐이므로 절반까지만을 사용한다. 
            for x in possible_set[i_half]:
                for y in possible_set[i-i_half]: # x와 y를 더하면 i 가 되도록 만든 수다. 
                    print(possible_set)
                    case_set.append(x+y)# 각 사칙연산 결과를 더한다.
                    case_set.append(x-y)
                    case_set.append(y-x)
                    case_set.append(x*y)
                    if y !=0:
                        case_set.append(x/y)
                    if x !=0:
                        case_set.append(y/x)
            if number in case_set:
                return i
            possible_set.append(case_set) # 최종 결과물 set에 사칙 연산 결과를 더한다.
    return -1 #N 이 8까지 답이 없으면 -1을 출력한다.