Programmers 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 합니다.

풀이

보아하니 Dynamic Programming 문제이다, 그렇다면 작은 문제로 어떻게 쪼갤 수 있을까?
사칙 연산 단위로도 쪼개야 할 것 같고 말야 우리가 원하는 것은 횟수가 가장 작은 경우이다

그렇다면 뭐를 저장하고, 뭐를 표로 그려야 하는가?

def solution(N, number):
    if N == number:
        return 1

    # DP 테이블 초기화
    dp = [set() for _ in range(9)]
    dp[1].add(N)

    for i in range(2, 9):
        dp[i].add(int(str(N) * i))  # 연속된 N 사용 (예: 55, 555)
        for j in range(1, i):
            for a in dp[j]:
                for b in dp[i - j]:
                    dp[i].add(a + b)
                    dp[i].add(a - b)
                    dp[i].add(a * b)
                    if b != 0:
                        dp[i].add(a // b)

            # 목표 숫자를 찾으면 해당 횟수 반환
            if number in dp[i]:
                return i

    return -1  # 8번 넘게 사용해도 목표 숫자를 못 만들면 -1 반환

코드 전체 구조

def solution(N, number):
    # 여기에는 solution 함수의 전체적인 구조와 각 부분의 역할이 설명됩니다.

# 예시 실행
print(solution(5, 12))  # 이 부분에서는 solution 함수를 테스트합니다.

Solution 함수

1. 기본 조건 검사:

   if N == number:
       return 1
   

   이 부분은 입력된 N이 number와 동일한 경우를 처리합니다. 같다면 N을 한 번만 사용하여 목표 숫자를 만들 수 있으므로 1을 반환합니다.

2. DP 테이블 초기화:

   dp = [set() for _ in range(9)]
   dp[1].add(N)
   

   dp라는 리스트를 만들어 각 인덱스에 숫자의 집합을 저장합니다. dp[1]은 N을 한 번 사용했을 때 만들 수 있는 숫자의 집합으로, 초기에는 N 자체만 포함합니다.

3. 메인 루프:

   for i in range(2, 9):
       dp[i].add(int(str(N) * i))  # 연속된 N 사용
       for j in range(1, i):
           for a in dp[j]:
               for b in dp[i - j]:
                   # 이 부분에서는 dp[i]에 새로운 숫자를 추가합니다.
   

이 부분은 N을 2회부터 8회까지 사용하는 모든 경우를 고려합니다.
먼저 N을 연속해서 사용하는 경우 (예: 55, 555)를 dp[i]에 추가합니다.
그 다음, 이전에 계산된 결과들을 이용하여 새로운 숫자를 만들고 dp[i]에 추가합니다.

4. 사칙연산 적용:

   dp[i].add(a + b)
   dp[i].add(a - b)
   dp[i].add(a * b)
   if b != 0:
       dp[i].add(a // b)
   

각 dp[j]와 dp[i-j] 집합의 원소들에 대해 사칙연산을 수행하여 dp[i]에 추가합니다.
나눗셈의 경우 분모가 0이 아닐 때만 수행합니다.

5. 목표 숫자 확인 및 반환:

   if number in dp[i]:
       return i
   

dp[i]에 목표 숫자 number가 있는지 확인합니다.
만약 있다면, 현재 i가 N을 사용한 최소 횟수이므로 i를 반환합니다.

6. 최종 반환:

   return -1  # 8번 넘게 사용해도 목표 숫자를 못 만들면 -1 반환
   

   만약 8번을 넘게 사용해도 목표 숫자를 만들지 못한다면 -1을 반환합니다. 이는 문제의 제한사항에 따른 것입니다.

예제의 입력 값에 따라 DP 테이블을 생성한 결과를 표로 나타내면 다음과 같습니다.

DP Index	생성된 숫자들의 집합
1
2
3
4
5	(비어 있음)
6	(비어 있음)
7	(비어 있음)
8	(비어 있음)

이 표에서 볼 수 있듯이, DP Index 4에서 12가 생성되었습니다.
이는 N을 4회 사용하여 number = 12를 만들 수 있음을 의미합니다. 따라서 이 경우의 최소 사용 횟수는 4입니다.

헷갈리지 말자

메인 루프에서는 N을 연속해서 사용하는 경우를 고려하고 있습니다.

그런데 여기서 N을 연속해서 사용한다는 것은 N을 i번 반복하여 이어붙인 숫자를 만든다는 의미입니다.

즉, N = 5이고 i = 2라면 55를 만들고, i = 3이라면 555를 만드는 것입니다.
이러한 숫자들은 각 DP Index에서 만들 수 있는 숫자들 중 하나입니다.

dp[i].add(int(str(N) * i))  # 연속된 N 사용

여기서 int(str(N) * i)는 N을 문자열로 변환한 후 i번 반복하여 연결하고, 다시 정수형으로 변환하는 과정을 거칩니다.
이는 N을 i번 연속해서 사용하여 만들 수 있는 숫자를 dp[i] 집합에 추가하는 것입니다.
예를 들어, N = 5이고 i = 3일 때, int(str(5) * 3)은 555가 됩니다.

이렇게 N을 연속해서 사용하는 숫자는 각 DP Index의 시작점에서만 고려되며, 그 후에는 이전 단계의 결과들과 사칙연산을 통해 새로운 숫자들을 생성합니다.
이렇게 해서 DP Index i에는 N을 i번 사용하여 만들 수 있는 모든 숫자들의 집합이 저장됩니다.