[프로그래머스]N으로 표현 - DP

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

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

 

def solution(N, number):
    # N과 number가 같은 경우라면 1을 반환한다.
    if N == number:
        return 1
    
    # N은 최대 8번까지 이용할 수 있으므로, 8개의 set(집합)을 가진 리스트를 만든다.
    dp = [set() for _ in range(8)]
    
    
    # N을 N번 나열하는 것에 대한 경우를 미리 초기화해서 넣어준다. 
    # 마지막에 추가하지 않는 이유는 해당 수를 사용해서도 사칙연산이 가능하기 때문이다.
    # [{5}, {55}, {555}, ...]
    for index, case in enumerate(dp, start=1):
        case.add(int(str(N)*index))
    
    # 최솟값이 8보다 클경우를 고려해 기본값으로 -1을 설정한다.
    answer = -1
    for i in range(8):
        for j in range(i):
            # N을 1 ~ N-1번 하는 경우와
            for op1 in dp[j]:
                # N을 N-1 ~ 1번 하는 경우와 사칙연산의 합집합을 구한다.
                for op2 in dp[i-j-1]:
                    dp[i].add(op1+op2)
                    dp[i].add(op1-op2)
                    # 나눗셈은 0으로 나눌 수 없다.
                    if op2 != 0:
                        dp[i].add(op1//op2)
                    dp[i].add(op1*op2)
        
        # number가 dp 안에 들어있다면, 그것이 최소 사용횟수이다.
        if number in dp[i]:
            answer = i + 1
            break

    return answer

해당 문제의 경우 제한사항을 통해 해결 방안을 도출해내는 것이 중요하다. 주요한 제한사항은 다음과 같다.

1. 사칙연산을 통해 수를 표현할 수 있다.
2. 사칙연산 이외에 2222 처럼 수을 나열하는 표현도 가능하다.
3. 8보다 클경우 -1을 return 한다.

위의 사항을 종합하면 다음과 같은 경우의 수를 생성해 낼 수 있다.

5을 1번 사용하여 만들 수 있는 숫자 경우의 수 : 5

5을 2번 사용하여 만들 수 있는 숫자 경우의 수 : 55, 5+5, 5-5, 5/5, 5*5

5을 3번 사용하여 만들 수 있는 숫자 경우의 수 : 555, 25+5, 25-5, 25/5, 25*5, 55+5, 55-5, 55/5, 55*5

 

즉, 5를 3번 사용하여 만들 수 있는 경우의 수 :

55(2번 나열) U (5를 1번 사용하여 만들 수 있는 경우의 수와, 5를 2번 사용하여 만들 수 있는 경우의 수의 사칙연산 결과)가 된다.

 

5를 N번 사용하여 만들 수 있는 경우의 수 :

5를 N번 나열 U (5를 1번, 5를 N-1번과 사칙연산) U (5를 2번, 5를 N-2번과 사칙연산) .... U (5를 N-1번, 5를 1번과 사칙연산)

으로 결론을 지을 수 있다.

 

최종적으로, 5를 8번 반복하여 만들 수 있는 경우의수를 만들어가면서 그 안에 number가 존재한다면 그것이 정답이다.

예외사항으로 N과 number가 같은 경우는 1을 return 한다.

 

문제 해결 Point

문제의 제한사항을 통해 N을 반복이용하면서 만들 수 있는 수들의 리스트를 DP에 담고, set을 통해 합집합의 기능을 구현한다.

제한사항을 통해 합집합과 경우의 수라는 규칙을 알아차리는 것이 가장 중요한 포인트인다.