문제풀이(Problem Solving)

프로그래머스, N으로 표현: C++ [CPP] ★★

게임이 더 좋아 2022. 3. 8. 09:18
반응형
728x170

 

처음엔 어려웠다.

왜냐면.. 나는 이전 것의 결과만 생각했다.

 

즉, [3] 을 구하기 위해서는 [1] 과 [2]의 사칙연산만 하면 되는 줄 알았으나..

교환법칙이 성립하지 않는 '/' 나눗셈과 '-' 때문에... [2]와 [1]도 계산해야했다.

나는 그것을 몰라서.. 다 틀렸다.

 

 

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

 


 

#맞는 풀이

#include <bits/stdc++.h>


using namespace std;

int solution(int N, int number) {
    int answer = -1;
    
    vector<vector<int>> vec(10);
    vec[1].push_back(N); // 문자 한개 쓰인 것 추가.
    if(number == N) return 1;
    
    int seq = 2;
    while(1){
        
        if(seq == 9)break;
        for(int i = 1; i<seq; i++){
            
            // ex) seq = 4이면  (1,3) (2,2) (3,1) 의 연산이 담김.
            for(auto& x : vec[i]){
                for(auto & y : vec[seq-i]){
                    vec[seq].push_back(x+y);
                    vec[seq].push_back(x-y);
                    vec[seq].push_back(x*y);
                    if(y == 0)continue;
                    vec[seq].push_back(x/y); //0이 아닐때만.
                }
            }
            
            //숫자 이어붙인것 마지막으로 추가
            string s = to_string(vec[seq-1].back());
            s += to_string(N);
            vec[seq].push_back(stoi(s));
            
            //target 값이 있는지
            auto it = find(vec[seq].begin(), vec[seq].end(), number);
            if(it != vec[seq].end())return seq;
        }
        
        //벡터 중복제거
        vec[seq].erase(unique(vec[seq].begin(),vec[seq].end()),vec[seq].end());
        seq++;
    }
    
    
    
    return answer;
}

 

다른 사람은 다르게 풀던데.. 난 이렇게 풀었다.

728x90
반응형
그리드형