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

문제

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

아래와 같이 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

크흠.. 괄호가 있지만.. 괄호는 연산 우선순위이기 때문에, 크게 의미는 없어보임..

최솟값이 8보다 커지면 -1를 리턴하는것 주의하고..

접근방법

5를 사용해서 만들 수 있는 조합방법은..

• 5
• 55/5 = 11
• 5*5 = 25

요정도..?의 숫자를 더 사용할 수 있다.

딕셔너리로 dic[사용숫자] = 5사용횟수

를 저장하면

dic[1] = 2 // 5/5

dic[1*5] = 1

dic[11] = 3

dic[11*5] = 2

dic[111*5] = 3

...

이를 딕셔너리에 넣어주고, dfs를 돌려주는 식으로 풀었다. number의 최대 수는 32000 임으로, 1111*n 까지만 봐줘도 충분하다고 생각했다.

하지만 bfs로 풀면 시간단축이 훨신 됨으로 bfs 풀이 또한 같이 올려본다.

코드

1.dfs풀이

2.bfs 풀이

3.평균적으로 시간대가 잘나왔던 밀쿄님 풀이