프로그래머스 문제 풀이 N으로 표현

이 문제는 이시윤 강사님의 프로그래머스 강좌 "파이썬을 무기로, 코딩테스트 광탈을 면하자!"를 보고 정리한 내용입니다.

문제 URL N으로 표현

Contents

1. 문제 지문 파악하기
2. 강사님의 알고리즘 풀이
3. 구르미의 알고리즘 풀이

문제 지문 파악하기

이 문제의 요점은 사칙연산을 통해서 number를 최소로 표현하는 N의 개수를 구하는 문제입니다. 먼저 예제를 들어서 문제를 파악해보도록 하겠습니다.

 

12 = 5 + 5 + (5/5) + (5/5)  (6개)
    = 55/5 + 5/5               (5개)
    = (55 + 5)/5                (4개)

12는 다음과 같이 6개의 5, 5개의 5, 4개의 5를 구할 수 있습니다. 즉 12를 표현하는 5로 이루어진 수식을 만들기 위해서 필요한 5의 최소 개수는 4개라는 뜻입니다. 어떻게 풀 수 있을까요?

 

우리는 일단 5를 최소 1번부터 8번까지 사용할 수 있습니다. 먼저 5를 1번 사용했을 때 만들 수 있는 수를 표현해봅시다.

 

5를 1번 사용해서 만들 수 있는 수 :
5

 

이번엔 5를 2번 사용해서 만들 수 있는 수를 표현해봅시다.

 

5를 2번 사용해서 만들 수 있는 수 :
55, 10(5+5), 0(5-5), 25(5*5), 1(5/5)

 

55는 그냥 연달아서 숫자를 만든 경우이고, 나머지 경우는, 1번 사용했을 때 만든 수들을 이용해서 사칙연산을 통해 만들 수 있는 수들입니다. 즉 다음과 같이 표현할 수 있습니다.

 

5를 2번 사용해서 만들 수 있는 수 :
55,            //5를 연속으로 이어붙인 수
10, 0, 25, 1 // 1번 SET 과 1번 SET 사칙연산한 결과 값들

 

여기서 잠깐! 숫자 2를 사칙 덧셈으로 표현해봅시다.

 

2 = 2
   = 1 + 1

 

N으로 표현하는 것도 이 법칙을 따라갑니다. 5를 2번 사용해서 만들 수 있는 수는 결국, 2개의 5를 연속으로 이어붙인 수와, 1번 SET과 1번 SET을 사칙연산을 통해 만들어지는 수들로 표현되는 것이죠.

 

계속해서 5를 3번 사용해서 만들 수 있는 수들은 다음과 같이 표현할 수 있습니다. 이번에는 거꾸로 3을 덧셈으로 표현해봅시다.

 

3 = 3
   = 1 + 2
   = 2 + 1

 

즉 5를 3번 사용하는 것은 다음과 같이 표현할 수 있습니다.

 

5를 3번 사용해서 만들 수 있는 수 (여기서, U는 합집합을 나타냅니다.) :
555 U
(1번 SET 과 2번 SET 사칙연산한 결과 값들) U
(2번 SET 과 1번 SET 사칙연산한 결과 값들)

 

여기서 중요한 점은 +, * 연산은 자리가 바뀌어도 같은 값이지만, -, / 연산은 자리가 바뀌게 되면 다른 수를 나타낸다는 점입니다. 결국 이렇게 표현할 수 있는 것이죠.

 

계속해서 5를 4번 사용해서 만들 수 있는 수들을 살펴봅시다. 4를 덧셈으로 다음과 같이 표현할 수 있습니다.

 

4 = 4
   = 1 + 3 
   = 2 + 2
   = 3 + 1

 

즉 4개의 5로 표현되는 수들은 다음과 같습니다.

 

5를 4번 사용해서 만들 수 있는 수 :
5555 U
(1번 SET 과 3번 SET 사칙연산한 결과 값들) U
(2번 SET 과 2번 SET 사칙연산한 결과 값들) U
(3번 SET 과 1번 SET 사칙연산한 결과 값들)

 

이 수식들을 숫자 N에 대해서 n번 사용했을 때 표현할 수 있는 수들을 일반화시키면 다음과 같습니다

 

N을 n번 사용해서 만들 수 있는 수 :
N을 n번 연달아서 사용할 수 있는 수 U
N을 1번 사용했을 때 SET 과 n-1번 사용했을 때 SET을 사칙연산한 수들의 집합 U
N을 2번 사용했을 때 SET 과 n-2번 사용했을 때 SET을 사칙연산한 수들의 집합 U
... U
N을 n-1번 사용했을 때 SET 과 1번 사용했을 때 SET을 사칙연산한 수들의 집합

 

n개의 N으로 표현할 수 있는 수들의 집합을 어떻게 구할지 아시겠나요? 이 문제는 즉, 1~8번까지 순회해서 만들어지는 수들의 집합 속에 number가 있는 최소 수를 찾아내기만하면 됩니다.

강사님의 알고리즘 풀이

위 지문 파악을 통해 만들어진 일반화를, 순서대로 표현하면 다음과 같습니다.

1. [ SET x 8 ] 인 리스트를 만듭니다. 각각 N을 1개로 표현하는 수들의 집합, 2개로 표현하는 수들의 집합, ... 8개로 표현하는 수들의 집합이 저장됩니다.
2. 8개의 SET에 개수만큼 N을 연달아 표현되는 수를 집어넣어줍니다.
3. 숫자 N에 대해서 n개를 사용해서 표현한 수의 일반화 수식을 코드로 표현합니다.
   1. i에 대해서 1-8까지 순회합니다.
      1. j에 대해서 0-i까지 순회합니다.
         1. j개를 사용해서 만든 수들의 집합 s[j]를 다음과 같이 순회합니다.
            1. i-j-1을 사용해서 만든 수들의 집합 s[i-j-1]를 다음과 같이 순회합니다.
               1. op1(s[j] 순회 수)과 op2(s[i-j-1] 순회 수)를 사칙연산합니다. 나눗셈 시 op2는 0이 되면 안됩니다.
               2. 사칙연산한 결과 값을 집합 s[i]에 추가합니다.
      2. 만약 number가 s[i]에 존재한다면, 반복을 멈추고 i+1번을 반환합니다.
   2. 8번을 순회했음에도, number를 못찾는다면, -1을 반환합니다.

이를 코드로 표현하면 다음과 같습니다.

 

def solution(N, number):
    # 허뎝님의 수정 피드백 -> 테스트 케이스가 바뀌면서 예외 사항을 추가해야 함.
    if N == number:
        return 1
        
    # 1. [ SET x 8 ] 초기화
    s = [ set() for x in range(8) ] 

    # 2. 각 set마다 기본 수 "N" * i 수 초기화
    for i,x in enumerate(s, start=1):
        x.add( int( str(N) * i ) )

    # 3. n 일반화
    #   { 
    #       "n" * i U 
    #       1번 set 사칙연산 n-1번 set U
    #       2번 set 사칙연산 n-2번 set U
    #       ...
    #       n-1번 set 사칙연산 1번 set, 
    #    } 
    # number를 가장 최소로 만드는 수 구함.
    for i in range(1, 8):
        for j in range(i):
            for op1 in s[j]:
                for op2 in s[i-j-1]:
                    s[i].add(op1 + op2)
                    s[i].add(op1 - op2)
                    s[i].add(op1 * op2)
                    if op2 != 0:
                        s[i].add(op1 // op2)

        if  number in s[i]:
            answer = i + 1
            break

    else:
        answer = -1

    return answer

 

구르미의 알고리즘 풀이

제 알고리즘 역시 강사님의 알고리즘과 일치합니다. 파이썬의 syntactic sugar가 들어있긴 합니다만, 결국 같은 알고리즘입니다.

 

파이썬 코드

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

    for i in range(1, 9):
        numbers = set()
        numbers.add( int(str(N) * i) )
        
        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

if __name__ == '__main__':
    N = 5
    number = 12
    result = solution(N, number)
    print(result)

 

다음은 CPP 코드입니다. CPP 코드는 강사님이 풀어주신 알고리즘을 바탕으로, 단순히 언어만 바꿨습니다.

#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <iostream>

using namespace std;

int get_basic_number(int N, int cnt) {
    int res = 0;
    
    while (cnt > 0) {
        cnt -= 1;
        res += N * pow(10, cnt);
    }
    
    return res;
}

int solution(int N, int number) {
    // 허뎝님의 수정 피드백 -> 테스트 케이스가 바뀌면서 예외 사항을 추가해야 함.
    if (N == number) {
        return 1;
    }
    
    int answer = -1;
    
    const int MIN = 8;
    //1. [ {} x 8 ] 초기화
    auto s = vector<set<int>>(MIN);
    // 2. 각 set마다 기본 수 "N" * i 수 초기화
    int idx = 1;
    
    for (auto & x : s) {
        x.insert(get_basic_number(N, idx));
        idx += 1;
    }
    
    //3. n 일반화
    //   { 
    //       "n" * i, 
    //       1번 set 사칙연산 n-1번 set, 
    //       2번 set 사칙연산 n-2번 set, 
    //       ...
    //       n-1번 set 사칙연산 1번 set, 
    //    } 
    // number를 가장 최소로 만드는 수 구함.
    for (int i=1; i<MIN; i++) { 
        for (int j=0; j<i; j++) {
            for (const auto & op1 : s[j]) {
                for (const auto & op2 : s[i-j-1]) {
                    s[i].insert(op1+op2);
                    s[i].insert(op1-op2);
                    s[i].insert(op1*op2);
                    
                    if (op2 != 0)
                        s[i].insert(op1/op2);
                }
            }
        }
        
        if (s[i].find(number) != s[i].end()) {
            answer = i+1;
            break;
        }
    }
    
    return answer;
}

int main(){
    int N = 5;
    int number = 12;
    auto result = solution(N, number);
    cout << result << endl;
    return 0;
}