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

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

/**
1. 빼기와 나누기의 경우 순서가 바뀌는경우 결과값이 달라진다.
처음에 최적화를 한답시고, i/2+1 까지만 돌렸다가, WA를 받았다. 
이 점을 확인 한 후 i-1까지 돌렸다.

2. newN(222,333,44444) 의 숫자를 만들고.... 만들어야 하는 최종 숫자와 비교를 하지 않았다.
단순한 실수인데... 반례를 찾느라 한시간이 걸렸다. ㅜㅜ
구현 도중에도 검사해야겠다는 생각을 하지 않았다.;;;;;;;;;;;;
**/

 

#include <string>
#include <vector>
using namespace std;
 
vector<int> v[9];
int solution(int N, int number) {
    if (N == number) return 1;
    for (int i = 0; i < 9; i++) {
        v[i].clear();
    }
    int newN = N;
    v[1].push_back(N);
    for (int i = 2; i < 9; i++) {
        newN = 10 * newN + N;
        v[i].push_back(newN);
        if (newN == number) return i;
 
        for (int j = 1; j < i; j++) {
            for (int a = 0; a < v[i - j].size(); a++) {
                for (int b = 0; b < v[j].size(); b++) {
                    if (v[i - j][a] == 0 || v[j][b] == 0) continue;
                    int res = v[i - j][a] + v[j][b];
                    v[i].push_back(res);
                    if (res == number) return i;
 
                    res = v[i - j][a] - v[j][b];
                    v[i].push_back(res);
                    if (res == number) return i;
 
                    res = v[i - j][a] * v[j][b];
                    v[i].push_back(res);
                    if (res == number) return i;
 
                    if (v[j][b] == 0) continue;
                    res = v[i - j][a] / v[j][b];
                    v[i].push_back(res);
                    if (res == number) return i;
                }
            }
        }
    }
    return -1;
}