시작하며😒

DP도 6개월만에 처음. 처음부터 생각보다 당황스러웠던 문제였어요.
예전 마지막 기억을 되살려 보면, 대개 1~2차원 배열에서 해결했던 거 같은데,
이 문제의 경우 뭔가 배열에 메모라이제이션을 하는데, 한 인덱스 안에 여러 개를 넣어야 하는 케이스였거든요...!

일단 몇 번 트라이할 때의 오답 과정을 거쳐, 결국에는 답지도 좀 참고하면서, DP를 다시 시작하는 데 불맛(?!)을 봤네요. 히히.
각설하고, 시작해볼까요?!

풀이 과정(오답 과정)

저는 원래는 오답이었어요. 다음과 같이 풀었거든요.
결국에는 왜 오답이었는지를 분석하는 것도 제 성장에 도움이 되니까, 귀찮으시다면 다음 목차로 넘어가주세요!!

1. 결국 최대 떠올릴 수 있는 해는 number * 9 안에 있다.
   (N은 9 이하이기 때문) 인덱스 계산 편의를 위해 1을 더하자.
2. 사칙연산을 각각 수행. 이를 메모라이제이션한다.
3. dp를 통해 사칙 연산하기 전의 기억한 배열을 비교, 작은 값에 대해 연산에 필요한 값을 배열에 넣는다.
4. 자기 기준으로 하면 될 거 같은데?!
   ex) n이 현재라면 -> n+N / n-N / n*N / n/N
5. 이를 answer이 8을 넘지 않을 경우, 답을 찾을 때까지 반복.

라고 생각했지요. 그런데 여기서 제가 간과한 게 있었어요. 그것은 바로,

사칙연산은 마지막 결과 값만을 가지고 연산을 하지 않는다.

라는 것이었죠!
가령, 30의 답이 나오려면, (25+5)만이 아니라, (5 * (1+5))의 순으로도 결과 값이 나오죠?!

따라서, 우리는 위의 아이디어로 접근하면 안됩니다...!

풀이 과정(이후)

그래서 다른 아이디어로 접근했어요. 결국 DP의 핵심은 점화식이니까요. 그리고 뭔가 문제에 좀 더 최적화하기 위해 답을 좀 참고하기도 했죠.

그리고 결국, 점화식의 핵심은 다음과 같았습니다.

1. count를 센다고 합시다. 이는 N이 사용된 개수를 나타낸 변수에요.
2. for문을 돌립니다. 이 count를 셀 때마다 결국 i개를 또 세개 되지요. 이는 0개~count개까지겠죠?!
3. 그렇다면 어떤 연산된 수에 사용된 N이 count개가 되려면 결국 N-count개를 사용해서 나온 결과값과 연산을 하면 되겠지요!!
4. 네, 계속 연산을 해줍시다. 결국 8개가 나오기 전에 이 연산 배열에 number이 나오면, 그게 최소 갯수겠죠?!

결국, count 를 산출하기 위한 점화식은

count = dp[i] + dp[count - i]

라고 할 수 있겠네요. 이를 풀어주면 됩니다.

코드

const solution = (N, number) => {
    const nCountArr = Array.from(new Array(9), (value, idx) => idx === 0 ? new Set() :  new Set([parseInt(`${N}`.repeat(idx))]));
    for(let i = 1; i < 9; i++) {
        for (let j = 1; j < i; j++) {
            for (const value of nCountArr[j]) {
                for (const anotherValue of nCountArr[i-j]) {
                    nCountArr[i].add(value + anotherValue);
                    if (value - anotherValue > 0) {
                        nCountArr[i].add(value - anotherValue);
                    }
                    if (value * anotherValue <= number * N) {
                        nCountArr[i].add(value * anotherValue);
                    }
                    if ((value % anotherValue) === 0) {
                        nCountArr[i].add(value / anotherValue);
                    }
                }
            }
        }
        if (nCountArr[i].has(number)) return i;
    }
    return -1;
}

마치며🌈

예전에 DP를 보면서 이런 생각이 들었던 게 떠올라요.

난 왜 이리 멍청하지...?

결국에는 어떤 패턴을 파악해서, 이 점화식이 전체까지 대입할 수 있는지만 잘 파악하면 되는데, 이를 제대로 못하는 듯 했거든요.
사실 모든 문제가 그런 거 같아요. 정말 어떤 핵심문제를 파악하고 해결하면 되는데, 그 패턴을 알 수 없는 노릇이니까요.

오늘도 좀 그런 기분을 느끼기는 했지만! 그래도 풀었다는 것에 만족하며, 이상 🖐