(프로그래머스 c++) 삼총사

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

프로그래머스

 

주어진 문제의 범위를 보면 3중 for문으로 풀 수 있지만,

다른 방식으로 접근할 수 있다.

 

주어진 number를 순회하면서, 값을 더할지 말지 결정하면 된다.

이를 결정하기 위해서는 vector를 선언하고, 이 vector는 {현재 num을 더한 결과, 더한 숫자의 개수}를 저장한다.

 

1. acc vector에는 아무것도 더하지 않은 값인 {0, 0}을 넣어준다.

2. number를 순회

3. 순회하면서 acc에 push_back을 해주기 때문에, 무한 루프에 빠지지 않기 위해 size를 미리 구한다.

4. 구한 size 만큼 acc를 순회

5. 현재 탐색하고 있는 숫자의 pair를 구조분해로 각각 first, second로 값을 미리 선언.

    만약 second가 3 미만이라면 acc에 {first + 현재 탐색하고 있는 num, second + 1}을 추가한다.

6. number를 모두 순회했다면 acc를 한번 순회한다.

    acc를 순회하면서 first == 0 and second == 3인 경우 answer을 +1 해준다.

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> number) {
    int answer = 0;
    vector<pair<int, int>> acc;
    
    acc.push_back({0, 0});
    
    for(auto num : number) {
        int size = acc.size();
        
        for(int i = 0; i < size; ++i) {
            auto [first, second] = acc[i];
            
            if(second < 3) {
                acc.push_back({first + num, second + 1});
            }
        }
    }
    
    for(auto a : acc) {
        if(a.first == 0 && a.second == 3) {
            ++answer;
        }
    }
    
    return answer;
}