[116일차] 프로그래머스 / N으로 표현하기

문제링크

Reference

이 문제는 저의 혼자힘으로 결국 풀지못했습니다..
이 블로그 의 코드를 전적으로 참조함을 명시합니다.

---

문제설명

이 문제는 이전에도 포스팅한 DP문제이다.
DP도 DP나름 기초적인 문제들도 있지만 이문제는 나에게 상당한 시련을 주었다.
나름 DP대로 풀겠지 했는데, 백트래킹을 이용해 접근하고 있었다.
문제해결 전략을 좀더 몸에 녹이고나서 고난이도 문제를 접해야겠다.
물론 DFS로 해결한 코드도 있다 경의를 표합니다.

우선 대략적인 문제접근방식은 이러하다.

---

숫자 한개를 사용했을 때 표현가능한 숫자는 N하나
숫자 두개를 사용했을 때 표현가능한 숫자는
NN
숫자 한개사용했을 때 (+ - / *) 숫자 한개사용했을 때
숫자 세개를 사용했을 때 표현가능한 숫자는
NNN
숫자 한개사용했을 때 (+ - / *) 숫자 한개사용했을 때 (+ - / *) 숫자한개사용 했을 때
숫자 한개사용했을 때 (+ - / *) 숫자 두개사용했을 때 ...
숫자 n개 사용했을 때 표현가능한 숫자는
'N' n번이어붙이기
숫자 한개사용했을 때 (+ - / *) 숫자 한개 ...
...
숫자 두개사용했을 때 (+ - / *) 숫자 한개 ....
...
숫자 n - 1개 사용했을 때 (+ - / *) 숫자 한개사용했을 때

---

문제에 보면 최소값이 8보다크면 -1을 리턴한다고 했다.
최대 8개 사용했을 때 까지의 경우의 수만 구하면 되는것이다.
관건은
각 개수대로의 경우를 set함수를 통해 저장하는것이다

예를들어 순회 차례(4)일 때 살피는것

1개일때

• (연산)1개인 경우
• (연산)2개인 경우
• (연산)3개인 경우

2개일때

• (연산)1개인 경우
• (연산)2개인 경우

3개일때

• (연산)1개인 경우

이런식으로 반복문을 구성해서 경우를 살핀다.

자바스크립트 코드

function solution(N, number) {
  //숫자 한개를 사용했을 때 표현가능한 숫자는 N하나
  //숫자 두개를 사용했을 때 표현가능한 숫자는 
    //NN
    //숫자 한개사용했을 때 (+ - / *) 숫자 한개사용했을 때
  //숫자 세개를 사용했을 때 표현가능한 숫자는
    //NNN
    //숫자 한개사용했을 때 (+ - / *) 숫자 한개사용했을 때 (+ - / *) 숫자한개사용 했을 때
    //숫자 한개사용했을 때 (+ - / *) 숫자 두개사용했을 때 ...
  //숫자 n개 사용했을 때 표현가능한 숫자는
    // 'N' n번이어붙이기
    //숫자 한개사용했을 때 (+ - / *) 숫자 한개 ...
    //...
    //숫자 두개사용했을 때 (+ - / *) 숫자 한개 ....
    //...
    //숫자 n - 1개 사용했을 때 (+ - / *) 숫자 한개사용했을 때
 
  //0번째 인덱스를 빈셋으로 비워준다. 자기자신도 넣어야되기때문
  const cases = [new Set()];
  //각 인덱스마다 모든 경우Set을 둔다
  for(let i = 1; i <= 8; i++){
    //자기자신을 붙인 케이스를 넣는다
    cases.push(new Set([Number(Array(i).fill(N).join(''))]))
    //예) i가 3일때 => 숫자 세개를 사용했을 때 표현가능한 숫자를 구할때
    for(let j = 1; j <= i; j++){
      //예) j가 1일때 =>숫자 세개를 사용한 경우중 숫자 한개 사용했을 때를 구한다
      for(const x of [...cases[j]]){
        for(const y of [...cases[i - j]]){
          //예) case[1] + case[2] , case[2] + case[1]
          cases[i].add(x + y)
          cases[i].add(x - y)
          cases[i].add(x * y)
          if(y)cases[i].add(~~(x / y))
        }
      }
      //
      if(cases[i].has(number))return i;
    }
  }
  return -1;
}
 
/* test */
console.log(solution(5, 12)) //----> 4

---

코드를 이해하고 다른사람들의 풀이들을 봤다.
set함수 진짜편하구나...