[프로그래머스(N으로 표현)]

https://programmers.co.kr/learn/courses/30/lessons/12973

코딩테스트 연습 - 짝지어 제거하기

문제 설명

문제 풀이

• 핵심은 N,NN,NNNN을 8자리수 까지 만든 후에 사칙연산 해야 한다는 것

재귀 방식 풀이

1. 8이상 반복할 수 없기 때문에 재귀의 방식을 사용하여 사칙연산을 해줄 수 있다.

동적 계획 법 풀이

1. 인덱스에 1~8까지 자릿 수 숫자를 미리 만든다. ex) num[2]=55
2. 1~8까지 반복하여 i만큼 N을 사용하여 만든 dp[i]를 구해나간다.(동적 프로그래밍)
   • m자 릿 수의 숫자와 사칙 연산을 한다고 가정 했을 때
     • num[m] 와 dp[i-m]배열 숫자를 사칙연산(+,-,*,/)하여 dp[i] 배열에 추가한다.
     • 메모이제이션을 활용하여 계산해 나간다.

 

 

//재귀 풀이

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int ans = -1;
int result_num;
void go(int num, int N, int index)
{

    if (num == result_num)
    {
        if (ans == -1 || ans > index)
        {
            ans = index;
        }
        return;
    }

    if (index == 8)
    {
        //8자리수에 도달하면 종료
        return;
    }

    int temp = 0;
    for (int i = 1; i + index <= 8; i++)
    {

        temp = temp * 10 + N;
        //8번 숫자를 추가하기 전까지 자릿수를 늘려가며 숫자를 만들어준다.

        go(num - temp, N, index + i);
        go(num + temp, N, index + i);
        go(num / temp, N, index + i);
        go(num * temp, N, index + i);
        //늘린 숫자길이 만큼 더해준다.
    }
}

int solution(int N, int number)
{
    result_num = number;
    go(0, N, 0);

    return ans;
}

 

 

//DP풀이

#include <iostream>
#include <string>
#include <vector>
#include <vector>

using namespace std;

int solution(int N, int number)
{

    int ans = -1;
    int num[9];
    int temp = 0;

    bool result = false;

    for (int i = 0; i < 8; i++)
    {
        temp = temp * 10 + N;
        num[i + 1] = temp;
        //자리수 늘린 값들 모두 구한다음 저장
    }

    vector<int> dp[10];
    dp[0].push_back(0);
    //계산위해 0을 임의로 넣어줌

    for (int i = 1; i <= 8; i++)
    {
        //1~8까지 반복

        for (int m = 1; m <= i; m++)
        {
            //1~i자리까지 만들어 진 수 , ex)5,55,5555

            for (int k = 0; k < dp[i - m].size(); k++)
            {
                //i-m의 만큼 사용 하면 만든 값 탐색하여 m자리수 만큼의 숫자를 계산하여 i배열에 넣어줌

                dp[i].push_back(dp[i - m][k] + num[m]);
                dp[i].push_back(dp[i - m][k] - num[m]);
                dp[i].push_back(dp[i - m][k] / num[m]);
                dp[i].push_back(dp[i - m][k] * num[m]);
            }
        }

        for (int k = 0; k < dp[i].size(); k++)
        {
            if (dp[i][k] == number)
            {

                return i;
            }
        }
    }

    return ans;
}

 

 

틀린 이유:

• 8번 사칙연산하여 N을 추가하는 DP 문제라고 잘못 풀었다.
• 55 5555와 같은 숫자를 만들어서 넣을 생각을 못했다..
• N이 0~9제한이고 NN,NNNN 와 같이 자리수가 늘어나는 방식은 temp = temp * 10 + N 와 같은 사용하면 편하다.