N으로 표현

프로그래머스의 'N으로 표현' 문제는 동적 계획법(Dynamic Programming, DP)의 전형적인 문제입니다. 이 문제의 핵심 아이디어와 풀이 과정을 정리해 드릴게요.

---

1. 핵심 아이디어: "사용 횟수별로 만들 수 있는 수의 집합"

이 문제는 N을 $k$번 사용해서 만들 수 있는 수들의 집합을 차례대로 구해 나가는 것이 핵심입니다.

1. DP[k] 정의: N을 $k$번 사용하여 만들 수 있는 모든 수의 집합(Set).
2. 연산 규칙: $k$번 사용하여 만든 수들은 다음의 조합으로 탄생합니다.
   • N을 $k$번 이어 붙인 수 (예: N=5일 때, $k=3$이면 555)
   • 사칙연산: $i$번 사용해서 만든 수들과 $(k-i)$번 사용해서 만든 수들을 서로 사칙연산 한 결과들.
     • 예: 3번 사용($k=3$) = (1번 사용 $\text{op}$ 2번 사용) $\cup$ (2번 사용 $\text{op}$ 1번 사용)
3. 최솟값 찾기: $k$를 1부터 8까지 늘려가며, 우리가 찾는 number가 해당 집합에 포함되는 순간의 $k$를 반환합니다.

---

2. 알고리즘 시각화

N을 사용한 횟수에 따라 집합이 어떻게 확장되는지 보여주는 구조입니다.

---

3. 파이썬 정답 코드 (상세 주석 포함)

Python

 

def solution(N, number):
    # number가 N과 같다면 1번만 써서 만들 수 있으므로 바로 1 반환
    if N == number:
        return 1
    
    # s[i]는 N을 i+1번 사용하여 만들 수 있는 수들의 집합(set)
    # 총 8번까지만 확인하면 되므로 8개의 집합을 초기화
    s = [set() for _ in range(8)]
    
    # 각 집합에 N을 i+1번 이어 붙인 수(NN, NNN 등)를 먼저 넣어줌
    for i, x in enumerate(s):
        x.add(int(str(N) * (i + 1)))
    
    # N을 사용한 횟수(i)를 1부터 8까지 늘려가며 확인
    for i in range(1, 8):
        # i번 사용해서 만든 결과는 j번 사용 결과와 (i-j)번 사용 결과의 사칙연산
        for j in range(i):
            for op1 in s[j]: # j번 사용해서 만든 수들
                for op2 in s[i - j - 1]: # i-j번 사용해서 만든 수들
                    s[i].add(op1 + op2) # 더하기
                    s[i].add(op1 - op2) # 빼기
                    s[i].add(op1 * op2) # 곱하기
                    if op2 != 0: # 나누기 (0으로 나누기 방지)
                        s[i].add(op1 // op2)
        
        # 현재 집합(i번 사용해서 만든 수들)에 목표 숫자 number가 있다면
        # i는 인덱스이므로 실제 사용 횟수인 i+1을 반환
        if number in s[i]:
            return i + 1
            
    # 8번까지 반복했는데도 못 찾았다면 -1 반환
    return -1

---

4. 이 문제의 포인트

• 중복 제거: set을 사용하여 계산된 결과값 중 중복된 숫자를 제거함으로써 연산 횟수를 획기적으로 줄입니다.
• 반복 범위: $i$번째 집합을 만들 때 $j$와 $i-j-1$의 조합을 찾는 이유는, 두 집합의 'N 사용 횟수 합'이 현재의 $i+1$과 같아야 하기 때문입니다.
• 조기 종료: 1번 사용할 때부터 순차적으로 계산하므로, 처음 number를 발견했을 때가 무조건 최솟값이 됩니다.