https://programmers.co.kr/learn/courses/30/lessons/42895

이 문제는 고민해봐도 풀리지 않아서 다른 분의 블로그를 참고했다. 많은 도움이 되어서 감사한 마음으로, 참고한 블로그를 이해하고자 손으로 공부한 내용과 풀이를 보면서 배운 점을 정리한다.

다른 사람의 풀이

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
    
    # 출처: https://gurumee92.tistory.com/164

주의할 점

8개의 set이 담긴 배열을 초기화해 줄 때 두 가지 방법으로 수행할 수 있다.

test = [set() for i in range(8)] # 방법 1
test2 = [set()]*8 # 방법 2

print(test) # [set(), set(), set(), set(), set(), set(), set(), set()]
print(test2) # [set(), set(), set(), set(), set(), set(), set(), set()]

방법 1과 방법 2는 똑같은 결과를 가지는 것처럼 보이지만, 주의해야 할 점이 있다. 자바스크립트의 배열이나 오브젝트를 등호(=)를 이용해 다른 변수에 복사했을 때와 같이, 방법 2로 리스트를 만든다면 test2 안에 들어있는 set들은 같은 값을 공유하게 된다.

test[0].add(1)
test2[0].add(1)

print(test) # [{1}, set(), set(), set(), set(), set(), set(), set()]
print(test2) # [{1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}]

test와 test2의 첫 번째 요소 set에 1을 추가한 후 출력해보면 이를 확인할 수 있다. 방법 1을 사용해서 리스트를 초기화하도록 하자.

회고

• DP 알고리즘을 제대로 이해하지 못한 채 스터디 숙제였기 때문에 어려운 문제에 섣불리 도전했다.
• 가장 쉬운 문제부터 차근차근 풀어나가며 개념을 이해한 다음 반드시 다시 풀어보자.
• 리스트를 정의할 때 실수할 수 있는 부분을 알게 되었다. 두 가지 초기화 방법의 차이를 제대로 알아두자.