[ programmers ] DP - N으로 표현

문제 링크

코딩테스트 연습 - N으로 표현

문제 풀이

N과 사칙연산만을 이용해 number를 표현할 수 있는 방법 중 N의 사용횟수 최솟값을 구한다.

조건

• 최솟값이 8이상이면 -1 반환
• N은 1이상 9이하, number는 1이상 32000 이하

IN

N 

number

OUT

N을 최소개 사용하여 number로 표현할때 N의 사용횟수

풀이

DP는 학과 알고리즘 수업 이후로 처음 풀어봤는데 생소하고 어렵더라,,

모르겠어서 블로그 글(https://gurumee92.tistory.com/164) 참고해서 풀어봄

N을 최대 8번까지 사용하여 number를 만드는데,

예제 1과 같이 N=5, number=12일때

**set1** 5를 1번 사용하는 경우 → 5

**set2** 5를 2번 사용하는 경우 → 5를 2번 붙힌 55와 5+5, 5-5, 5*5,  5/5

→ 이때 set2는 5를 2번 붙히기 + set1의 원소 (+-*/) set1의 원소 

**set3** 5를 3번 사용하는 경우 → 5를 3번 붙힌 555와 5+55, 5-55, 5*55, 5/55, 55+5, 55-5, 55*5, 55/5

→ 이때 set3는 5를 3번 붙히기 + set1의 원소 (+-*/) set2의 원소 + set2의 원소 (+-*/) set1의 원소 

→ set n에 대해 일반화시키면,

: set n은 5를 n번 붙히기 + set1의 원소 (+-/) set n-1의 원소 + set2의 원소 (+-/) set n-2의 원소 + ... + set n-1의 원소 (+-*/) set 1의 원소

따라서~

1. 8개의 set 생성

2. 각 set마다 N을 i번 붙힌 값 add

3. for문 돌면서 i번째 set에 j번째 set의 원소 (+-*/) i-j-1번째 set의 원소 한 값 add

   3.1 해당 set에 number에 해당하는 값 있으면 answer값 갱신 후 break

로 접근해서 풀면 된다.

def solution(N, number):
    answer = -1
    
    if N == number:
        return 1
    
    #n을 1번부터 8번 사용한 set의 초기화
    s = [set() for _ in range(8)]
    for i,x in enumerate(s, start=1):
        x.add(int(str(N) * i))
    
    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
    return answer