[JS] 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	number	return
5	12	4
2	11	3

 

접근 방법

일단 동적 계획법 문제는 어떤 규칙성을 발견해내는게 중요합니다.예시에 나온 대로 12를 만드는 가장 최소의 경우의 수는 4이고, 그 예시는 (55 +5) /5 입니다.

반대로 올라가보죠. 그렇다면 5를 3개 가지고 있는 경우에서 60, (55 + 5)을 가지고 있어야 하겠군요.

 

이런 생각을 한다는게 쉽지 않습니다. 누가 5를 4개 갖고 12를 만드는 문제를 보고

"아 5를 3개 만들었을 때 경우에서 사칙연산한 결과에서 원하는 답을 골라낼 수 있겠군!"

이런 생각을 할까요? 그래도 익숙해져야죠 어떻게 하겠습니까ㅎ

 

결론적으로 N이 9 이하이기 때문에

1. 배열을 9개만들고, 각 값의 초기값으로 index만큼의 number를 넣어서 저장. (ex. N = 3 => 555 이런느낌)
2. N이 2라면 1일때 모든 요소에서 사칙연산을 한 값을 저장.
3. 그리고 중복 제거.(set을 쓰면 좋겠네요)

이런 식으로 bottom-up 방식으로 쭉쭉 가야겠네요. 그러다가 원하는 값을 발견한다면 과감하게 return 해야겠습니다.

정답 코드 같이 보시죠.

 

정답 코드

function solution(N, number) {
    const memo = Array.from({length: 9}, () => new Set());
    if (N === number) return 1;
    memo.forEach((sets, i) => {
        if (i !== 0) sets.add(Number(String(N).repeat(i)));
    });
    for (let i = 1; i < 9; i++) {
        for (let j = 1; j < i; j++) {
            for (const origin of memo[j]) {
                for (const value of memo[i - j]) {
                    memo[i].add(origin + value);
                    memo[i].add(origin - value);
                    memo[i].add(origin * value);
                    memo[i].add(origin / value);
                }
            }
        }
        if (memo[i].has(number)) return i;
    }
    return -1;
}

 

딱히 설명할 것도 없네요. 코드가 너무 직관적입니다.

동적 계획법은 진짜 많은 유형을 접해봐야할 것 같습니다.

 

그럼 이만!