🧮

N으로 표현

레벨

LV.3

날짜

Oct 9, 2023

링크

https://school.programmers.co.kr/learn/courses/30/lessons/42895

🔎 문제

school.programmers.co.kr

https://school.programmers.co.kr/learn/courses/30/lessons/42895

🧩 구현과정 및 코드

개인 토글 영역에 구현 과정과 코드를 자유롭게 작성해주시면 됩니다.

사용할 데이터 구조와 풀이 방향성

적용할 알고리즘 혹은 메서드

수영

구현

use 배열: index를 개수라고 생각하고, [[use1 사칙 연산 결과], [use2, 사칙 연산 결과], …] → 중복값 제외 Set 사용

코드

정은

구현

결과 배열의 각 idx는 N을 쓴 횟수

결과 배열의 value는 해당 N을 idx만큼 써서 나올 수 있는 결과값들 ⇒ 중복 방지를 위해 set이용

dp[nCount] = dp[1]와 dp[nCount-1]를 사칙연산 ~ dp[nCount-1]와 dp[1]를 사칙연산

코드

종혁

구현

코드

재웅

구현

작은 수로 큰 수를 찾는 DP? 백트래킹?

N을 i개 사용해 연산했을 때의 값을 dp[i]에 넣어줌

중복 고려하지 않아도 되기 때문에 집합 구조 사용

코드

✏️ 후기

문제를 풀고 느낀 점, 막혔던 부분 혹은 개선 사항 등을 자유롭게 작성해주시면 됩니다.

👧🏻

수영

Set을 쓰면 연산이 줄어들겠구나

for문을 줄일 수 있는 방법이 있을까?

👧🏻

정은

(시행착오1) 앞에 연산 결과에 원소 하나를 추가해서 이 둘을 사칙연산해 풀었었다.

괄호를 어떻게 표현하는가가 관건이었다..

(시행착오2) NNN 처럼 붙이는 것도 앞의결과*10+N 로 풀었었다.

생각해보면 초기값으로 NNN..(nCount)만 잘 넣어주면, 이전 dp 원소에 이미 N, NN, NNN..(nCount-1)가 있으므로 알아서 잘 연산한다.

늘 그랬지만 구현 로직들이 생각보다 간단한게 신기하다. dp를 많이 풀어서 익숙해져야 할 것 같다.

👦🏻

종혁

문자열을 똑같이 붙이는 과정에서 padStart()가 유용할것 같다

👦🏻

재웅


function solution(n, number) {
    const answer = [];
    // use는 n의 사용 개수 8까지, Set 중복값 제거
    let use = Array.from(new Array(9), () => new Set());
    
    if(n === number){
        return 1;
    } else {
        // use 배열 [{5}, {55}, ..., ]
        use.forEach((element, index) => {
            if (index !== 0) {
                element.add(Number(String(n).repeat(index)))
            }
        });
				// 사칙연산 결과값 저장
        for(let i = 1; i <= 8; i++) {
            for(let j = 1; j < i; j++) {
                for(let item1 of use[j]) {
                    for(let item2 of use[i - j]) {
                        use[i].add(item1 + item2);
                        use[i].add(item1 - item2);
                        use[i].add(item1 * item2);
                        use[i].add(Math.floor(item1 / item2));
                    }
                }
            }
						// 결과값에 number가 있으면 i return, 없으면 i++ 사칙연산 수행
            if (use[i].has(number)) {
                return i;
            }
        }
				// n이 8이상이면 -1 return
        return -1;
    }
}


function solution(N, number) {
    let results = [0]; //결과 배열(이하 주석에는 dp[]로 대신

    for (let nCount=1; nCount<=8; nCount++) { //8번이 최대
            results[nCount] = new Set([Number(String(N).repeat(nCount))]); //초기값은 5를 nCount만큼 붙인 것

            for (let i=1;i<nCount;i++) { //dp[nCount] = dp[1],dp[nCount-1] ~ dp[nCount-1],dp[1]
                for(const prev1 of results[i]) { //좌측 dp의 결과들
                    for(const prev2 of results[nCount-i]) { //우측 dp의 결과들 
                        results[nCount].add(prev1+prev2);
                        results[nCount].add(prev1-prev2);
                        results[nCount].add(prev1*prev2);
                        results[nCount].add(Math.floor(prev1/prev2));
                    }
                }
            }

            if (results[nCount].has(number)) {
                return nCount;
            }
        }
    return -1;
}


function solution(n, number) {
   //d[i] - N을 i번 사용했을 때 만들 수 있는 수들의 집합(set 자료구조로 중복 제거)
    const d = Array.from(Array(9),() => new Set())
    if(n === number){
        return 1
    }
    d[1] = [n]
    let double = n + 10*n
    d[2].add(double)
    d[2] = [double,n+n,n*n,n/n]//n을 1~2번 사용하는 경우는 직접 초기화
    for(let i=3;i<=8;i++){//3번~8번
        if(double === number){
            return i-1
        }
      double = double + 10 ** (i-1) * n
      d[i].add(double)
    for(let j=1;j<i;j++){
        for(let first of d[i-j]){
        for(let second of d[j]){
        d[i].add(first + second)
        d[i].add(first - second)
        d[i].add(first * second)
        d[i].add(Math.floor(first / second))}
			//dp[4] - dp[1]과 dp[3]을 사칙연산 (5 + 555 , 5+ (55 + 5),....)
			//			- dp[2]와 dp[2]를 사칙연산
}
 if(d[i].has(number)){
            return i //발견하면 return
        }
}

    }
    return -1
}


function solution(N, number) {
    const dp = Array(9).fill(0).map(v => new Set());
    
    for(let i=1; i<9; i++){
        dp[i].add(Number(String(N).repeat(i)));
        
        for(let j=1; j<i; j++){
            // dp[7] = dp[1] + dp[6] or dp[2] + dp[5] or dp[3] + dp[4]
            for(const currentVal of dp[j]){
                for(const opponentVal of dp[i-j]){
                    dp[i].add(currentVal+opponentVal);
                    dp[i].add(currentVal-opponentVal);
                    dp[i].add(currentVal*opponentVal);
                    dp[i].add(currentVal/opponentVal);
                }
            }
        }
        if(dp[i].has(number)) return i;
    }
    return -1;
}