[프로그래머스] (LV3) n으로 표현

N으로 표현

Python3

문제 설명

아래와 같이 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일 테스트케이스가 추가되었습니다.

풀이

---

python

answer = -1
def solution(N, number):
    
    def sol(count, result):
        global answer
        temp = N

        if count > 8 : return
        if result == number :
            if answer > count or answer == -1:
                answer = count
                return
        
        for i in range(8-count):
            
            sol(count+i+1, result + temp)
            sol(count+i+1, result - temp)
            sol(count+i+1, result * temp)
            sol(count+i+1, int(result / temp))
            
            temp = (temp * 10) + N
            
    sol(0,0)
    return answer

설명

---

난이도 3의 DP(Dynamic Programming, 동적 계획법) 문제다.
처음 접했을때 약 4번이나 풀이 방법을 바꿔가며 풀어봤지만 모두 실패했다.

처음엔 BFS 처럼 사칙연산 기호들을 이어붙이는 식으로 풀이를 해보려 했다가 낭패를 봤다.

두 번째에는 딕셔너리를 활용해 연산값을 계속 저장하며 문제를 풀어보려 시도했다. 결과는 역시나 실패. 테스트 케이스 몇 개가 끝까지 해결이 안되었다. 여기서 괄호의 개념을 도입해야 한다는 판단이 들었는데, 이마저 BFS 형식으로 구현하면 시간초과가 날 것이 분명했다. 또한 풀이때 연산 방향에 신경썼는데 지금 생각해보면 전혀 필요 없는 부분이라 그땐 왜 그랬는지 모르겠다. 집중력이 저하된 것 같다.

세 번째 방법은 위에서 쓴 딕셔너리 내의 두 값을 자발적으로 비교하는 방식으로 진행했다. 역시나 풀리지 않는 테스트 케이스들과 시간 초과로 실패했다. 이론상 N값을 이용해 4번의 사칙연산 결과만 저장해 놓으면, 나머지 값들의 비교로 최대 8의 결과값을 구할 수 있다. 그러나 4번째의 딕셔너리 연산이 시간초과를 불러왔다.

네 번째 방법은 위 세 번째 방법과 네 번째 방법을 합쳐서 활용했는데, 풀면서도 절대로 이런식의 풀이가 성공할리 없다는 확신이 들었다. 풀이가 구질구질(?)해지면 거진 실패를 했기 때문에, 그 감정이 스멀스멀 올라오기 시작했을때 손을 놓고 다른 방법을 강구했다.

결국 해법은 비슷한 유형의 문제 풀이를 보고 찾을 수 있었다. 사실 구현 자체만 보면 모든 부분을 탐색하기 때문에 BFS 풀이의 느낌이 강하다.

핵심은 temp 변수에 있다. 두 값을 단순히 붙이는 방법을 자리수 이동으로 해결하고, 이를 연산의 한 방법으로 사용한 것이 굉장히 창의적이여서 이해하기 힘든 부분이었다. 풀이 과정이 간단하니 코드 또한 훨씬 줄고 깔끔해졌다. 두고두고 다시 봐야할 풀이 같다.