N으로 표현 python - [프로그래머스/DP 알고리즘]

문제 내용 요약

아래와 같이 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, NN, NNN ~ NNNNNNN]의 숫자를 활용하여 모든 사칙연산을 했을 때 최소한의 N을 쓰는 값을 구해라.

N을 1~7번 사용했을 때의 사칙연산 계산하는 모든 경우의수를 구하는 규칙을 알아야한다

N이 5일 경우 1번 사용하는 경우
5

N이 5일 경우 2번 사용하는 경우
a +-*// b는 a에 대해서 b를 사칙연산 계산한다는 것
계산전 : 55, 5 +-*// 5  
계산후 : 55, 10, 0, 25, 1

N이 5일 경우 3번 사용하는 경우
계산전 : 555, 5 +-*// 55, 5 +-*// 10, 5 +-*// 0, 5 +-*// 25, 5 +-*// 1,  순서바꿔서 55 +-*// 5, 10 +-*// 5, 0 +-*// 5, 25 +-*// 5, 1 +-*// 5

- 발견한 규칙 -
555를 제외하고 나머지 경우의 수는
(1번 사용하는 경우) +-*// (2번 사용하는경우)
(2번 사용하는 경우) +-*// (1번 사용하는경우)

N이 5일 경우 4번 사용하는 경우 규칙

5555를 제외하고 나머지 경우의 수는
(1번 사용하는 경우) +-*// (3번 사용하는경우)
(2번 사용하는 경우) +-*// (2번 사용하는경우)
(3번 사용하는 경우) +-*// (1번 사용하는경우)

N을 1 -> 7번까지 사용하면서 Target(number)이 가장먼저 발견되는 집합의 순서를 리턴하면 N의 최솟값

글씨를 잘 못씁니다.

 

구현해야 하는 코드방식

집합간의 사칙연산을 위해서는 아래 인덱스를 출력해야한다.

 

집합간의 사칙연산

1 1  # N이 2개일때

1 2, 2 1   # N이 3개일때 

1 3, 2 2, 3 1   # N이 4개일때

1 4, 2 3, 3 2, 4 1 # N이 5개일때

1 5, 2 4, 3 3, 4 2, 5 1 # N이 6개일때

1 6, 2 5, 3 4, 4 3, 5 2, 6 1 # N이 7개일때

for i in range(1,8):
	for j in range(1,i):
         	print(j,i-j)

문제풀이

N = 5
number = 12

# 중복된 값을 제거하기 위해 set() 집합을 사용
list_s = [set() for i in range(8)]

val = 0

# N이 1~7번 등장했을 경우에 따라 5, 55, 555, 5555 ~ 5555555 삽입
for i in range(1,8):
    val = val * 10 + N
    list_s[i].add(val)
    

# 아래처럼 값이 나오는 알고리즘을 구현해야함
# 4번일 경우 -> [1 3] [2 2] [3 1] 
# 5번일 경우 -> [1 4] [2 3] [3 2] [4 1]

for i in range(1,8):
    print("N의 갯수", i)
    for j in range(1,i):
        print(j, i-j)
        for val1 in s[j]:
            for val2 in s[i-j]:
                list_s[i].add(val1 + val2)
                list_s[i].add(val1 - val2)
                list_s[i].add(val1 * val2)
                if val2 != 0:
                    list_s[i].add(val1 // val2)
                    
    if number in s[i]:
        answer = i
        break
    else:
        answer = -1
        
print(answer)

깨달은점

아직은 그저 어렵습니다.. 처음에 이걸 경우의수 다 하면 너무 느리지 않을까 걱정하면서 어떻게 해야하지 고민했는데 다른사람 풀이를 보니 실제로 모든 경우의 수를 구하는데..Bottom Up 방식으로 구현해 최소한의 작업을 줄이면서 푸는것을 이해했습니다. 

추가적으로, 이런 규칙을 발견하는 부분이 중요한데 이 부분이 어려운거 같습니다.