[알고리즘 스터디] programmers, 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 합니다.

[풀이]

첫 번째.

문제 갈래에도 DP가 명시되어 있기 때문에 DP를 이용해서 푸는 문제임은 확실하다..!

 

어떻게 DP를 이용할 것인가?

 

N=5일 때를 생각해보자.

1. 5 한 개 -> 5

2. 5 두 개 -> 55, 5+5, 5-5, 5*5, 5/5

다섯배로 늘어나는 것 처럼 보이지만,

뒤에 5를 붙이는 것과, 나머지 연산은 앞뒤 순서에 따라 결과가 달라지게 된다.

3. 5 세 개

->555, 555, 55+5, 55-5, 55*5, 55/5, 5/55

   55+5, 5+55, (5+5)+5, (5+5)-5, (5+5)*5, (5+5)/5, 5/(5+5) 

   55-5, 5-55, (5-5)+5, (5-5)-5, (5-5)*5, (5-5)/5, 5/(5-5)

   55*5, 5*55, (5*5)+5, (5*5)-5, (5*5)*5, (5*5)/5, 5/(5*5)

   55/5, 5/55, (5/5)+5, (5/5)-5, (5/5)*5, (5/5)/5, 5/(5/5)

이렇게 다음 단계로 넘어갈 때 약 7배씩 늘어나게 된다. 

 

그렇다면 각 단계에서 나온 값들을 어떤 형태로 저장할 것인가? 

1. 수를 두 덩어리로 보관

2. 각 덩어리가 수인지, 계산식인지 표시 

(하나의 수라면, 5를 붙여 자릿수를 추가할 수 있다. 수식이라면 사칙연산만 가능하다)

 

각 단계가 넘어갈 때 마다, 이전단계의 값들은 계속 남겨둘 필요가 없다. 

매 단계마다 저장공간 초기화하기. 

 

vector에 각 단계의 수들을 저장하자. 

vector 한 칸의 구성 [num1, num2, flag1, flag2, result]

ex) 55+(5-5) 

num1 = 55

num2 = 0

flag1 = 1

flag2 = 0

(flag가 1이면 숫자, 0이면 계산식, -1이면 존재하지 않는다는 의미)

(55의 경우, num2가 존재하지 않기 때문에, flag2=-1로 해두어 num2를 이용하지 않게 한다)

result = 55

 

vector안에 result가 number과 같은 칸이 생기면 종료(return 반복횟수)

or

반복 횟수가 8을 넘어가면 종료(return -1)