[프로그래머스/Python] 동적계획법(DP) - N으로 표현

문제 지문 파악하기

• 5를 최소 1번부터 8번까지 사용할 수 있음
• 5를 1번 사용해서 만들 수 있는 수: {5}
• 5를 2번 사용해서 만들 수 있는 수:
  = 5를 연속으로 2번 이어붙인 수 + 5를 1번 사용해서 만들 수 있는 수들의 사칙연산
  = {55(5를 연속으로 이어붙인 수), 10 (5+5) , 0 (5-5), 25 (5*5), 1 (5/5)}
• 5를 3번 사용해서 만들 수 있는 수
  = 5를 연속으로 3번 이어붙인 수
  +5를 1번 사용해서 만들 수 있는 수와 5를 2번 사용해서 만들 수 있는 수의 사칙연산
  + 5를 2번 사용해서 만들 수 있는 수와 5를 1번 사용해서 만들 수 있는 수의 사칙연산
  = {0, 2, 4, 5, 6, 555, -20, -4, -50, 15, 11, 50, 275, 20, -5, 60, 125, 30}

일반화 해보면,

• N을 n번 사용해서 만들 수 있는 수:
  = N을 연속으로 n번 이어붙인 수
  + N을 1번 사용해서 만들 수 있는 수와 n-1번 사용해서 만들 수 있는 수의 사칙연산한 수들의 집합
  + N을 2번 사용해서 만들 수 있는 수와 n-2번 사용해서 만들 수 있는 수의 사칙연산한 수들의 집합
  + ...
  + N을 n-1번 사용해서 만들 수 있는 수와 1번 사용해서 만들 수 있는 수의 사칙연산한 수들의 집합

풀이

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)
		# i = 1) numbers = {5}
        # i = 2) numbers = {0, 1, 10, 55, 25}
        # i = 3) numbers = {0, 2, 4, 5, 6, 555, -20, -4, -50, 15, 11, 50, 275, 20, -5, 60, 125, 30}
        # i = 4) numbers = {0, 1, 2, 3, 130, 5, -250, 7, -120, 9, 10, 11, 6, 4, 270, 15, 16, 12, 20, 150, 280, 25, 26, 24, -100, 30, 35, 550, 300, 45, 560, 50, 5555, 54, 55, 56, 65, -55, -54, 75, 80, 3025, -45, -9, 2775, -550, 1375, -30, 100, -25, -24, 250, -20, 110, 111, -15, -270, 625, -2, -10, 120, -6, -5, -4, -3, -1}
        if number in numbers:
            answer = i
            break
        
        DP.append(numbers)
    return answer

Python 문법

집합 자료형: set

• 순서가 없음, 중복을 허용하지 않음, 인덱싱이 되지 않음
• 집합 자료형의 원소에 접근하는 방법

1. 리스트로 변환 후 인덱싱을 이용해서 접근
2. 튜플로 변환 후 인덱싱을 이용해서 접근

A = set('abc')
 
print(list(A)[0])   # a
print(list(A)[1])   # b
print(list(A)[2])   # c

print(tuple(A)[0])   # a
print(tuple(A)[1])   # b
print(tuple(A)[2])   # c

• 교집합:&, intersection
  • 집합의 순서 상관없음

A = set(['a','c',1,4])
B = set(['c',1,5,'9'])
print(A&B)                # {1, 'c'}
print(A.intersection(B))  # {1, 'c'}

• 합집합: |, union
  • 집합의 순서 상관없음

A = set(['a','c',1,4])
B = set(['c',1,5,'9'])
print(A|B)         # {1, 4, 5, 'c', 'a', '9'}
print(A.union(B))  # {1, 4, 5, 'c', 'a', '9'}

• 차집합: -, difference
  • 집합의 순서 상관있음

A = set(['a','c',1,4])
B = set(['c',1,5,'9'])
print(A-B)             # {'a', 4}
print(A.difference(B)) # {'a', 4}
print(B.difference(A)) # {5, '9'}

• remove/ add/ update 메소드
  • 집합자료형은 한번 생성되면 결코 수정되지 않는다
  • 즉! 기존에 있던 원소를 삭제하고 다시 새로운 것을 만들어야 함
  • .remove(제거할 인자)
  • 하나의 원소 추가는 .add(추가할 인자)
  • 한꺼번에 여러 개의 원소 추가는 .update(추가할 인자)

A = set(['a','c',1,4])
A.remove(1)
print(A) # {'c', 4, 'a'}

A.add('b')
print(A)   # {'a', 4, 'b', 'c'}

A.update([0,9])
print(A)   # {0, 'a', 4, 9, 'b', 'c'}