[프로그래머스] .dp - N으로 정수 표현

안녕하세용

오늘 dp 로 넘어가는 역사적인 날입니당

물론 익숙하지 않은 문제 접근 방식에 혼자서 풀지는 못했지만 ...

시도 해봤다는 것만으로도 너무 행복한 날입니당 ㅎㅎ

 

* 제가 작성해가는 풀이는 아래의 블로그를 참고한것입니당 *

https://gurumee92.tistory.com/164

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

 

문제

 

풀이

 

이 문제의 요점은 사칙연산을 통해서 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의 최소 수는 4입니다.

우리는 어떻게 다른 임의 수 N과 숫자에 대해서, 최솟값을 구할 수 있을까요?

 

우리는 이 문제가 dp 라는 것에 집중할 필요가 있습니다.

dp의 경우 단계적으로 풀이해내가면 정답을 찾을 수 있습니다.

 

우리는 일단 5를 한번만 사용하는 경우를 생각해봅시다.

 

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

 

그 다음으로 5를 두번 사용하는 경우를 생각해봅시다.

 

• 5를 2번 사용해서 만들 수 있는 수 : 55, 5+5, 5-5, 5*5, 5/5 

2번 사용하는 경우를 주목해봅시다.

맨 처음 55는 그냥 5를 연속해서 쓴 수입니다.

그러나 그 이후의  5+5, 5-5, 5*5, 5/5 는 5를 1번 사용해서 만들어진 수에 사칙연산으로 이어준 값입니다!

 

즉 이를 표현하면 다음과 같습니다.

 

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

 

우리는 향후 구현의 쉬움을 위해,

5를 2번 사용할 경우, 이 때의 2를 덧셈으로 나타내어볼 필요가 있습니다 :)

 

2 = 1 + 1

 

이렇게 나타내는 이유에 대한 감이 오시나요?

 

모르셨더라도 괜찮습니다! 저도 몰랐거든요 ...

 

우리가 5를 2번 사용해서 만들수 있는 수를 만들 때, 간단히 5를 연속으로 이어서 만들기도 했습니다.

그런데 이미 만들어진 1번 set과 1번 set을 사칙 연산하여 만들었는데요 !

이 때의 1과 1은, 2의 덧셈 값이었다는 겁니다 !!!

 

즉, 앞으로 나타낼 3, 4, 5 의 수에 대해서 값을 만들 때, 각 수의 사칙 연산 값이 이용됩니다 !

 

감이 오신다면 한번 5를 3번 이용했을 경우에 대해서도 알아볼까요 ?

 

그럼 먼저 3을 덧셈으로 표현해보겠습니다.

 

3 = 1 + 2
   = 2 + 1

 

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

 

5를 3번 이용해서 만들 수 있는 수 :
555,                                                 // 5를 연속으로 이어 붙인 수
(1번 set과 2번 set 을 사칙연산으로 이어 붙인 결과 값들),
(2번 set과 1번 set 을 사칙연산으로 이어 붙인 결과 값들),

 

여기서 1번과 2번 set을 순서를 바꿔가며 사칙연산을 만들어 주는데에는, 

덧셈이나 곱셈은 순서를 바꾸어도 값이 변화가 없지만 뺄셈이나 나눗셈의 경우 순서가 값에 영향을 끼치기 때문입니다.

 

이제 한번 더 나아가 봅시다.

 

5를 4번 이용해서 만들 수 있는 수를 구할 것입니다.

 

먼저 4를 덧셈으로 나타내겠습니다.

 

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

 

이를 이용해서 5를 4번 이용해서 만들 수 있는 수는 아래와 같을 것입니다.

 

5를 4번 이용해서 만들 수 있는 수 :
5555,                                                 // 5를 연속으로 이어 붙인 수
(1번 set과 3번 set 을 사칙연산으로 이어 붙인 결과 값들),
(3번 set과 1번 set 을 사칙연산으로 이어 붙인 결과 값들),
(2번 set과 2번 set 을 사칙연산으로 이어 붙인 결과 값들)

 

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

 

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

 

N은 8번까지만 반복해주면됩니다!

왜냐하면, 문제에서 8을 넘으면 -1을 return 하라고 해주었으니까요 ~!

 

위를 이해한 후 코드를 써내려 가면 다음과 같은 논리가 됩니다.

 

1. [ set X 8 ] 인 list를 만듭니다. 여기에는 N을 1개로 표현하는 수들의 집합, 2개로 표현하는 수들의 집합.. 8개로 표현하는 수들의 집합이 저장됩니다.

2. 숫자 N에 대해서 n개를 사용하여 표현한 일반화 수식을 코드로 표현합니다.

   i 에 대해서 1-8까지 순회합니다.

      j에 대해서 0-i까지 순회합니다.

         j개를 사용해서 만든 수들의 집합 s[i]를 다음과 같이 순회합니다.

         op1(s[j] 순회 수) 과 op2(s[i-j-1] 순회 수) 를 사칙연산합니다. 나눗셈시 op2는 0이 되면 안됩니다.

         사칙 연산한 결과 값을 집합 s[i]에 추가합니다.

 

   만약 numbers 가 s[i]에 존재한다면 반복을 멈추고 i+1을 반환합니다.

 

3. 8번을 순회했음에도, 발견하지 못했다면 -1을 반환합니다.

 

 

코드

def solution(N, number):
    if N == number:
        return 1
    #set * 8 초기화
    s = [ set() for x in range(8)]
    
    #각 set에 N을 i번 사용했을 때 N이 i번 연속되는 기본 수 넣기
    for i,x in enumerate(s,start=1):
        x.add(int(str(N)*i))

    # {
    # "N" * i 
    #     U
    # 1번 set 사칙연산 n-1번 set 
    #     U
    # 2번 set 사칙연산 n-2번 set
    #     U
    #...
    # n-1번 set 사칙연산 1번 set
    # }

    for i in range(1, 8):
        #print("i=",i)
        for j in range(i):
            #print("j=",j)
            for op1 in s[j]:
                #print("This is op1 : ","s[",j,"]","=",op1)
                for op2 in s[i-j-1]:
                    #print("This is op2 : ","s[",i-j-1,"]","=",op2)
                    s[i].add(op1 + op2)
                    s[i].add(op1 - op2)
                    s[i].add(op1 * op2)
                    if op2 != 0:
                        s[i].add(op1 // op2)
        #print("s[" ,i,"]=",s[i])                

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

 

하루빨리 dp에 익숙해지기를 기도하며 ...

포스팅을 마치겠습니다 :)

 

모두 모두 화이팅입니당