[Algorithm] 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 합니다.

입출력 예

5	12	4
2	11	3

 

✏️ 풀이

전형적인 DP문제라고 생각했다. 

 

먼저 배열(canMakeNum)을 하나 선언했다. 이 배열이 의미하는 것은 인덱스는 사용하는 숫자의 개수이고, 각 요소는 Set 자료구조로 되어 있어 만들 수 있는 수를 의미한다. 처음 초기화할 때 숫자를 이어붙인 수(만약 숫자가 1, 사용한 개수가 2라면 11)를 할당해줬다. 길이는 9인데 사용한 숫자가 8개를 넘어가면 -1을 리턴하라는 조건이 있었기 때문이다.

 

1부터 8까지 반복문을 수행한다. 이는 사용한 숫자의 개수를 의미하고 내 로직은 만들 수 있는 숫자들을 모두 만들어 Set에 넣어주고 그 안에 목표로 하는 숫자가 있는지 확인한다. 이 때 계산법은 다음과 같다.

 

• 2라는 숫자를 1번 사용했을 때: {2}
• 2라는 숫자를 2번 사용했을 때: {22, 4(2+2), 0(2-2), 1(2/2), 4(2*2)} -> {22, 4, 0, 1}

일 때 숫자를 3번 사용해서 만들 수 있는 숫자는 1번 사용했을 때와 2번 사용했을 때의 요소들을 서로 사칙연산해주면 된다.

 

• 222
• 22+2, 22-2, 22/2, 22*2
• 4+2, 4-2, 4/2, 4*2
• 0+2, 0-2, 0/2, 2*2
• 1+2, 1-2, 1/2, 1*2

순서대로 나열하면 {222, 24, 20, 11, 44, 6, 2, 2, 8, 2, -2, 0, 4, 3, -1, 0.5, 2} 가 되는데 여기서 중복을 제거하고, 나눗셈의 몫만 사용하면 {222, 24, 20, 11, 44, 6, 2, 8, -2, 0, 3}가 된다.  

 

이 때 주의해야 하는 것은 위의 계산들은 (2번 사용했을 때의 숫자) 사칙연산 (1번 사용했을 때의 숫자)로 2번 사용했을 때의 숫자들이 앞에 나오는데 나눗셈이나 뺄셈은 숫자의 영향을 받기 때문에 반대의 과정을 진행해줘야 한다. 현재의 예시에서는 예외가 없으나, 다른 수에서는 다를 수 있다.

 

• 2+22, 2-22, 2/22, 2*22
• 2+4, 2-4, 2/4, 2*4
• 2+0, 2-0, 2/0, 2*0
• 2+1, 2-1, 2/1, 2*2

만약 4번 사용한 숫자를 계산하기 위해서는 다음과 같은 과정을 거친다.

• (1번 사용한 숫자) 사칙연산 (3번 사용한 숫자)
• (2번 사용한 숫자) 사칙연산 (2번 사용한 숫자)
• (3번 사용한 숫자) 사칙연산 (1번 사용한 숫자)

나는 이때 경우의 수를 조금이라도 줄이기 위해 음수는 포함하지 않았다.

 

계산되어 만들 수 있는 숫자를 담은 Set 자료구조가 완성되면 목표로 한 숫자가 있는지 확인하고 있다면 answer를 사용한 숫자로 할당하고 break 시켜줬다.

⌨️ 코드

function solution(N, number) {
  var answer = -1;
  if (N === number) return 1;
  const canMakeNum = [...Array(9)].map((_, i) => new Set([parseInt(String(N).repeat(i))]));

  for (let i = 1; i < 9; i++) {
    for (let j = 1; j < i + 1; j++) {
      for (const num1 of canMakeNum[j]) {
        for (const num2 of canMakeNum[i - j]) {
          canMakeNum[i].add(num1 + num2);
          canMakeNum[i].add(num1 * num2);
          if (num2) canMakeNum[i].add(Math.floor(num1 / num2));
          if (num1 - num2 > 0) canMakeNum[i].add(num1 - num2);
        }
      }
    }

    if (canMakeNum[i].has(number)) {
      answer = i;
      break;
    }
  }

  return answer;
}