[DP] N으로 표현

https://school.programmers.co.kr/learn/courses/30/lessons/42895?language=javascript 

프로그래머스

로직

수를 만들어내는 방법

사칙연산 (+, -, *, /)와 숫자를 붙여서 만드는 방법

 

• i+1길이의 배열을 만들어 i번째에 N을 i개 사용하여 만들 수 있는 모든 수를 추가한다.
  • 문자열.repeat(n번) 
• 먼저 i 번쨰 set에 숫자N을 i번 붙여만든 수를 추가한다 (5, 55, 555, 5555....) = i는 N을 사용한 갯수이다
• 2개의 N으로 만들 수 있는 수는 55, 5+5, 5-5, 5*5, 5/5다
• 3개의 N으로 만들 수 있는 수는
  • 555
  • 1개의 N으로 만든 수와 2개의 N으로 만든 수의 사칙연산과
  • 2개의 N으로 만든 수와 1개의 N으로 만든 수의 사칙연산이다 (5 - 55 !== 55-5 이라 사칙연산의 순서도 고려해야한다.)
• 4개의 N으로 만들 수 있는 수는 
  • 5555,
  • 1개의 N으로 만든 수와 3개의 N으로 만든 수의 사칙연산,
  • 2개의 N으로 만든 수와 2개의 N으로 만든 수의 사칙연산,
  • 3개의 N으로 만든 수와 1개의 N으로 만든 수의 사칙연산이다

 

이런식으로 i = 8일때까지 각 i에 대해 가능한 연산들을 저장해서 i개의 N으로 만들 수 있는 수를 기억한다.

그 중에 타켓 숫자가 나오면 i를 리턴한다

i가 8보다 크면 -1를 리턴한다.

 

 

set 은 for of 가능하다

const sets = Array.from({length: 9}, () => new Set());

[
    Set(1) { '' },
    Set(1) { '5' },
    Set(1) { '55' },
    Set(1) { '555' },
    Set(1) { '5555' },
    Set(1) { '55555' },
    Set(1) { '555555' },
    Set(1) { '5555555' },
    Set(1) { '55555555' }
]

for (const s of set) {
	console.log(s) // sets[0], sets[1], sets[2]....
}

 

 

전체코드

function solution(N, number) {
    const sets = Array.from({length: 9}, () => new Set());
    // 5, 55, 555 ...추가
    sets.forEach((set, i) => {
        set.add(Number(String(N).repeat(i)));
    })
    
    for (let i = 1; i <= 8; i++) {
        for (let j = 1; j <= i; j++) { //
            for (const first of sets[j]) {
                for (const second of sets[i-j]) {
                    sets[i].add(first+second);
                    sets[i].add(first-second);
                    sets[i].add(first*second);
                    sets[i].add(Math.floor(first/second));
                }
                if (sets[i].has(number)) return i;
            }
        }
    }
    return -1;
}