[Python] 프로그래머스 Lv 3 - N으로 표현

 

DP 문제인데, 단순히 메모이제이션을 하지 않고 조금 다른 방식으로 풀어야 하는 특이한 문제였다.

프로그래머스 강의 내용 바탕으로 주석 추가하여, 내용을 정리하였다.

문제

(아 뭐 이리 문제 매워)

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

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

 

알고리즘

정신이 아득해지는 까다로운 문제이다. 처음 접근할때는 9 * 32001 이중리스트를 만들어야 하나 고민했는데 이걸 계산하고 최솟값을 계산하는거 자체가 무리라는 생각이 들었다.

따라서, 그냥 앞의 값을 바탕으로 계산을 때리는 알고리즘만이 가능할 것이다.

1개만 쓰는 경우는 자명하고,
2개만 쓰는 경우는 숫자 2개를 붙이는 경우와 1개인 경우와 1개인 경우를 연산,
3개를 쓰는 경우는 숫자 3개 붙이는 경우와 2개 경우와 1개 경우의 연산..

이런식으로 일반화가 가능할 것이다. 전부 다 따지는 방법 외엔 답이 없다. 다행인것은 제약조건에서 8개까지로 연산을 한정시켰다.

최솟값을 구하는 것은 무리기에, 처음으로 그 숫자가 만들어지면 바로 계산을 스톱시키고, 정답 개수를 반환하는 식으로 코드를 작성하면 된다.

 

코드

def solution(N, number):
    s = [set() for x in range(8)] # 우선 8개의 집합을 만들어둔다.
    for i, x in enumerate(s, start = 1): # 초기 자명한 1, 11, 111, 케이스...
        x.add(int(str(N) * i))
    for i in range(1, 8):  # 2개짜리부터 8개짜리에 대해
        for j in range(i):  # 각 케이스별로 1개~N-1개 대응
            for num1 in s[j]:  
                for num2 in s[i-j-1]: # 개수 합을 맞춰버려.
                    s[i].add(num1+num2)
                    s[i].add(num1-num2)
                    s[i].add(num1*num2)
                    if num2 != 0:  # 나누기 주의
                        s[i].add(num1//num2)
        if number in s[i]: # 그래서 목표가 나와버리면 그 즉시 종료하되
            answer = i + 1
            break
    else:
        answer = -1
        
    if number in s[0]:  # 2개인 경우부터 세서 초항 예외처리
        answer = 1

    return answer