N으로 표현_프로그래머스 lv3

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

프로그래머스

이 문제는 처음에 완전탐색으로 하나하나 풀었었다. 

하지만, 완전탐색으로는 (5*5)+(5/5) 같은 케이스를 도저히 풀어내지 못하겠어서 어떤 블로그를 참고했다.

 

 

 

1. 풀이방법

 

n = 5일때

cnt	value
1	5
2	55	5*5	5+5	...
3	555	55*5	55+5	...
...

 

 이 풀이방법은 vector<set<int>>dp에 5 55 555 같은 이어붙인 수들은 따로 넣고 나머지 계산부분들은 

for(int i = [1 ~ cnt)) 라는 반복문을 만들고 dp[cnt]에 dp[i] (+, - / *) dp[cnt-i] 를 넣어 풀었다.

 

 

2. 코드

 

#include <string>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

vector<set<int>> dp(10);

int getConnectedNum(int n, int r)
{
    int result = n;
    for (int i = 1; i < r; i++)
        result = result * 10 + n;
    return result;
}

int solution(int N, int number) {
    int answer = 0;
    int maxCnt = 9;

    for (int cnt = 1; cnt < maxCnt; cnt++)
    {
        dp[cnt].insert(getConnectedNum(N, cnt));

        for (int i = 1; i < cnt; i++)
        {
            for (auto& c1 : dp[i])
            {
                for (auto& c2 : dp[cnt - i])
                {
                    dp[cnt].insert(c1 + c2);
                    dp[cnt].insert(c1 - c2);
                    dp[cnt].insert(c1 * c2);
                    if (c2 != 0)
                        dp[cnt].insert(c1 / c2);
                }
            }
        }
    }

    for (int i = 1; i < maxCnt; i++)
    {
        if (dp[i].count(number) != 0)
        {
            answer = i;
            break;
        }
    }
    //cnt 8안에서 찾을수 없는경우
    if (answer == 0)
        answer = -1;

    return answer;
}

 

3. 후기

 

쉬운거 같은데 처음 방향을 잘못잡아서 개고생했다..ㅠ