[프로그래머스] 동적계획법 1. N으로 표현

---

풀이

어렵다 ㅠ 레벨 3..,

 

처음 생각한 로직은 이렇다.

numbers는 연산을 해서 나온 결과값을 키로 갖고 value로는 그 수가 나올 때까지 사용된 N의 개수이다.

첫 번째 반복문은 연산의 횟수로 최대 8번까지 돌아간다.

두 번째 반복문에선 이전 연산 결과값들에 N을 사칙연산한다. 그러니까 한 번 더 연산하고 numbers에 추가한다.

number를 찾으면 반환한다.

def solution(N, number):
    numbers = { N: 1 }
    num_of_n = 2
    
    while True:
        for item in list(numbers):
            if item*N not in numbers:
                numbers[item*N] = num_of_n;
            if item+N not in numbers:
                numbers[item+N] = num_of_n;
            if item-N not in numbers:
                numbers[item-N] = num_of_n;
            if item//N not in numbers:
                numbers[item//N] = num_of_n;

        num_of_n += 1;

        if num_of_n >= 9:
            return -1;
        
        if number in numbers:
            return numbers[number];

55처럼 사칙연산이 아닌 같은 수로 묶인 경우를 잊고있었다.

 

그래서 두 번째로 생각한 방법

처음에 8까지 N을 이어붙인 딕셔너리를 만들어놓는다

ex 5: 1, 55: 2, 555: 3, 5555: 4, 55555: 5, 5555555….

저 딕셔너리 for문돌려서 자기자신 key 값과 사칙연산,

그 딕셔너리 값에 기존에 하던 대로 N과 사칙연산

결과값이 없으면 추가하고 있다면 누가 더 작은지 비교해서 작은 값으로 value 업데이트

number 찾으면 리턴

 

그런데 이거 구현해도 뭔가 안 될 것 같다는 생각이 들었다.

그래서 다른 사람 아이디어만 찾아서 읽어보았다. (출처: velog.io/@j_user0719/N%EC%9C%BC%EB%A1%9C-%ED%91%9C%ED%98%84-PYTHON)

 

• N이 i 개 만큼 있는 set을 만들어 준다.
• dp[1] 일 경우, {5} , dp[2] 일 경우 {5+5, 5-5, 5//5, 5*5}이기 때문에 이전(dp[1])의 구성요소의 사칙 연산 결과로 구성 되어있다.
• 이처럼 dp[3]을 해보면, 555 , (dp[1] 연산 dp[2]) , (dp[2] 연산 dp[1])이 되는것을 볼 수 있다.
• 만들어진 dp[i] set 에서 number이 존재하면 i를 반환.
• 끝까지 발견 못하면 -1을 출력

오호!! 나는 결과 값을 key, 사용된 N의 개수를 value로 가졌는데

이건 반대로 dp[사용된 N 개수] = {결과 값들} 의 형태였다. 연산 수 마다 결과값을의 집합을 가지니 깔끔하게 정리가 된다..!

다음에 뭔가 하다가 잘 안 풀리면 뒤집어 보기도 해야겠다.

만약 내가 생각한 방식대로 구현했다면 자기 자신과 연산하므로 연산 횟수가 순차적으로 들어가지 않을 것이고 쓸데없는 연산을 많이 했을 것이다. 아마 구현했어도 시간으로 컷 당했을 듯.,,

 

또 다른 아이디어로는... n번의 N 사용에는 i번의 N 사용된 값들과 n-i번의 N이 사용된 값들의 연산 값이라는 것이다. 다들 매우 똑똑하시다.

 

아이디어대로 구현했다.

import math

def solution(N, number):
    numbers = [ set() for _ in range(9)]
    
    for i in range(1, 9):
        numbers[i].add(int(str(N) * i))
        for j in range(1, i):
            for x in numbers[i-j]:
                for y in numbers[j]:
                    numbers[i].add(x*y)
                    if y != 0: numbers[i].add(x//y)
                    numbers[i].add(x+y)
                    numbers[i].add(x-y)
    
    for i in range(1, 9):
        if number in numbers[i]:
            return i
    return -1

통과!