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

🧩 문제 : N으로 표현

 

💡 문제 포인트

1️⃣ 사용횟수가 8보다 크다면 -1 return 

2️⃣ 나누기 연산에서 나머지는 무시 

3️⃣ +, * 연산은 자리가 바뀌어도 같은 값이지만 -, / 연산은 자리가 바뀌게 되면 다른 값이 나온다.

 

---

 

💪🏻 풀이 과정 

🌱 아이디어 

1️⃣ 주어진 숫자 N으로 횟수당 만들 수 있는 조합을 만든다. 

2️⃣ 만들어진 숫자 조합에 number로 주어진 숫자가 있는지 확인 후 있다면 횟수를 리턴한다. 

3️⃣ 없다면 횟수를 하나씩 늘려 다시 가능한 숫자 조합을 만들고 위 내용을 반복한다.

 

📍 N = 2, number = 11인 경우의 예제를 살펴보자. 

N을 1번 사용해 얻을 수 있는 조합 

2

N을 2번 사용해 얻을 수 있는 조합 

22,

2 + 2, 2 * 2, 2 / 2, 2 - 2

N을 3번 사용해 얻을 수 있는 조합

222,22 + 2, 22 * 2, 22 - 2, 22 / 2,(2 + 2) + 2, (2 + 2) * 2, (2 + 2) / 2, (2 + 2) - 2,

(2 * 2) + 2, (2 * 2) * 2, (2 * 2) / 2, (2 * 2) - 2,

(2 - 2) + 2, (2 - 2) * 2, (2 - 2) / 2, (2 - 2) - 2,

(2 / 2) + 2, (2 / 2) * 2, (2 / 2) / 2, (2 / 2) - 2

 

여기서 패턴을 하나 찾을 수 있다. 

바로 전 횟수의 수를 사칙 연산 한다는 것 !

 

 

💻 코드

def solution(N, number):
    answer = -1
    DP = []

    for i in range(1, 9):
   		# 각 횟수마다 값을 담을 set에 기본 수 N을 i번 반복한 수 삽입
        numbers = set()
        numbers.add( int(str(N) * i) )
        
        # number를 가장 최소횟수로 만들기
        for j in range(0, i-1):
            for x in DP[j]:
                for y in DP[-j-1]:
                    numbers.add(x + y)
                    numbers.add(x - y)
                    numbers.add(x * y)
                    
                    if y != 0:
                        numbers.add(x // y)

        if number in numbers:
            answer = i
            break
        
        DP.append(numbers)

    return answer

 

💭결과