상세 컨텐츠

본문 제목

프로그래머스 문제 풀이 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;
}

 

관련글 더보기

댓글 영역

  • 프로필 사진
    2020.02.15 23:28
    설명이 이해가 잘안가는데.. 1번 SET 과 1번 SET 사칙연산한 결과 값들 <- 이말이 뭘뜻하는건지를
    모르겠네요..
    • 프로필 사진
      2020.03.07 16:43 신고
      1번 SET은 1개의 5로 표현할 수 있는 수입니다. 즉 5이죠.

      그렇다면 1번 SET과 1번 SET을 사칙 연산하는 것은 { 5 } 와 { 5 } 를 이용해서 만든 수들이라고 보면 됩니다. 즉 2개의 5로 만들 수 있는 수들이죠. 즉 1번 SET끼리 연산한 결과는 다음과 같습니다.

      { 5+5, 5-5, 5*5, 5/5 }

      이것이 바로 2번 SET입니다. 단어 선택이 오해의 소지가 충분했군요. 질문해주셔서 감사합니다. 이해가 안되신다면 다시 답글 달아주세요
  • 프로필 사진
    2020.06.26 16:22 신고
    공부하는 데에 많은 도움이 되었습니다^^
    제가 공부 시작한지 얼마 되지 않아 set는 한 번도 사용해 본 적이 없어서, 익숙한 vector로 변경해보니 통과가 되더라구요.
    혹시 set을 고르신 이유가 따로 있으시다면 답변 남겨주실 수 있을까요?
    • 프로필 사진
      2020.06.27 11:43 신고
      도움이 되었다니 정말 다행입니다.

      set을 쓴 이유는, vector와 달리 기본적으로 같은 값의 중복을 방지하기 때문에 썼습니다. vector를 쓰면 아마 같은 값이 여러번 돌아서 for문을 더 돌게 될거라 생각합니다. 이런 부분에서 연산 속도를 올려보고자 해서 set을 썼습니다.

      감사합니다.
  • 프로필 사진
    2020.09.25 22:14
    안녕하세요 ! 명쾌한 설명 정말 감사드립니다.
    그런데 c++ 코드 테케 1개를 통과를 못시키더라구요 ㅠㅠ
    뭘까 생각했는데 N == number인 경우를 걸러내지 못하더라구요
    4중 for문 돌기 전에 N==number이면 1을 리턴하는 코드가 추가되어야 할 것 같습니다!
    • 프로필 사진
      2020.10.01 14:58 신고
      피드백 감사합니다. 허뎝님.

      제가 문제를 풀었을 때랑 테스트 케이스가 변하면서 에러가 났었네요. 허뎝님 덕분에 정상 코드로 제출할 수 있었어요.

      추가적으로 저의 경우엔, for 문 돌기 전에 그러니까 문제 시작과 동시에 예외 사항을 제거하는 방식으로 해결하였습니다.
  • 프로필 사진
    2020.10.03 21:16
    4 부분에 오타가 있습니다. 1 + 1 이 아니라 1 + 3이 되어야 할 것 같습니다.
    잘 공부하고 갑니다.
  • 프로필 사진
    2021.02.07 20:54 신고
    좋은 정리 감사합니다 👍 x 100
  • 프로필 사진
    2021.02.17 17:37
    강사님풀이 3번에 "j개를 사용해서 만든 수들의 집합 s[j]를 다음과 같이 순회합니다." 에서
    j+1 개를 사용해서가 맞는것같습니다
  • 프로필 사진
    2021.05.17 16:41 신고
    덕분에 좋은 공부 되었습니다 감사합니다
  • 프로필 사진
    2021.06.22 14:47 신고
    감사합니다. 답답했는데 속 시원히 해결했네요! 글 퍼갑니다! 문제되면 삭제하겠습니다!
  • 프로필 사진
    2021.12.18 15:36
    for문에 const auto&을 사용하신 이유가 궁금합니다..
    • 프로필 사진
      2021.12.18 16:29 신고
      음 일종의 코드 컨벤션이라고 보시면 됩니다 ^^

      개인적으로 참조 타입을 받기 때문에 const로 고정해두는 것이 좋겠다라고 생각해서 이렇게 코드를 작성했어요.

      제가 cpp를 잘 사용하지는 않아서 맞는 컨벤션인지는 모르겠네요 ㅎㅎ;;