[프로그래머스 Lv3/파이썬] N으로 표현(DP), (테케 2번, 9번)

 

[프로그래머스 Lv3/파이썬] N으로 표현

문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)

12 = 55 / 5 + 5 / 5

12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.

이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

N number return

5	12	4
2	11	3

입출력 예 설명

예제 #1

문제에 나온 예와 같습니다.

예제 #2

11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

※ 공지 - 2020년 9월 3일 테스트케이스가 추가되었습니다.

 

---

 

[내 풀이]

※ 소요시간 : 30 분

※ 풀이 전략

-  
    dp[i] 계산하기 : dp [i] 는 아래의 케이스들을 모두 고려한 값이다. 
    dp[1] +-*/ dp[i-1]
    dp[2] +-*/ dp[i-2] 
    .
    .
    .
    dp[i-1] +-*/ dp[1]
- 1차 시도 실패 원인 : 예외 케이스를 고려하지 못했기 때문에. 1과 관련된 값은 항상 한번 더 생각해야한다. (TC 9: 5,5 =>1)  

- 2차 시도 실패 원인: 예외 케이스를 고려하지 못했기 때문에. 처음 구한 dp에 이미 구하려는 값 number가 있는 경우. 내 코드 상에서는 for문(2~9) 에서 새로 업데이트 되는 numbers에 대해서만 체크했기 때문에, 이런 문제가 발생 

def solution(n, number):
    
    # dp[i]: i번 사용해서 얻을 수 있는 수들의 집합 
    dp = [set([int(str(n)*i)]) if i>0 else set() for i in range(9)] # 0~8 까지의 dp 

    # 1차 수정: 예외 케이스[tc: 9], 이후에 range를 2~9로 도니까, 예외 상황 생각해야 함
    if n==number: 
        return 1
    # 2차 수정: 예외 케이스[tc: 2], 처음 dp구한 것에 이미 구하려는 값 number가 있는 경우
    for i,x in enumerate(dp):
    	if number in x:
        	return i
    
    for i in range(2, 9):
        numbers = set()
        for j in range(1, i):
            for x in dp[j]:
                for y in dp[i-j]:
                    numbers.add(x+y)
                    numbers.add(x-y)
                    numbers.add(x*y)
                if y!=0:
                    numbers.add(x//y)
        if number in numbers: #i가 작은 것 부터 시작하기 때문에 가장 작은 경우는 자연스레 가장 먼저 구해진다. 
            answer = i
            break
        dp[i].update(numbers)
    else: #그냥 return -1 해도 되지만, 좀 더 명확하게 전달하기 위해 return은 하나만 쓰고, answer를 업데이트 하자 
        answer = -1    
    return answer

 

※ 중요 포인트

- 리스트 컴프리헨션 안에서 if와 else를 모두 써야할 경우 for문의 앞에 작성해야 한다. 

    dp = [set([int(str(n)*i)]) if i>0 else set() for i in range(9)]

- dp 테이블의 i번째 에는 i와 관련된 어떤 값이 들어갈까를 항상 생각해야한다. 

- 중간에 에러가 있었다.

2023.12.01 - [알고리즘 문제풀이/요약 정리] - [파이썬 에러] ValueError: invalid literal for int() with base 10:

---

[다른 사람의 풀이]

참고한 풀이

https://gurumee92.tistory.com/164

프로그래머스 문제 풀이 N으로 표현