Step 6-2: Python 풀이 예제 보기

학습 주제
코딩테스트 연습
동적계획법 N으로 표현

학습 내용
4겹으로 되어있지만, 기존에 만들어 두었던 답을 이용하고, 중복을 제외함.
+, -의 경우 앞과 뒤를 바꾸었을 때 값이 동일 하기 때문에 이를 줄일 수 있게 순회를 조정 할 수 있지만 코드의 가독성을 위해 효율성을 다소 포기함.
마찬가지로 number도 N번째를 위한 모든 경우의 수를 확인한 후 N번 사용 집합 내 값이 있을 때 확인함.

N = 5
number = 12
# 중복을 모으고 수를 모으기 위한 데이터 타입인 set
# s = [set()] * 8 은 안됨.
# x 에는 1번 사용해서 만들 수 있는 집합, 2번 사용해서 만들 수 있는 집합... 8번 사용해서 만들 수 있는 집합이 들어간다
# index는 0 부터 시작하지만 계산만 잘 하면 문제 X
s = [set() for x in range(8)]
print(s)
# i 는 1부터 시작하는 정수
for i, x in enumerate(s, start=1):
    # 각각의 set에다가
    # 5, 55, 555를 각 set에 미리 깔아놓고 시작
    x.add(int(str(N) * i))
for i in range(1, len(s)):
    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

N을 1번 사용한 값은 N 자체 하나이기 때문에 알고 있다고 가정하고 바로 2번 사용을 구하는 계산부터 시작함.
for문을 4번 사용하는 만큼. 헷갈리기 쉽다.