[algorithm] 백준 2309번 일곱난쟁이

 

처음에는 배열의 원소를 이중 for문으로 추적하면서

2가지 원소를 찍고 그 원소들을 제외한 나머지들의 합이 100이되는 경우를 찾아보려했는데

도저히 구현이 안되고 코드가 복잡해졌다.

 

알고보니 반대로 원소들의 전체 합에서 2가지 원소를 뺀 값이 100이 되는 경우를 생각하면 되는 것이였다

 

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

int main() {
    vector<int> vec;    
    
    for (int tmp=0; tmp<9; tmp++)
        {
            int value;
            cin >> value;
            vec.push_back(value);
            
            
        }
    
    int sum = accumulate(vec.begin(), vec.end(), 0);

    for (int i=0; i<9; i++)
        {
            for (int j=(i+1); j<9; j++)
                {
                    if (sum - (vec[i]+vec[j]) == 100) 
                        {
                           if (i < j)
                           {
                               vec.erase(vec.begin()+j);
                               vec.erase(vec.begin()+i);
                           }
                           else
                           {
                               vec.erase(vec.begin()+i);
                               vec.erase(vec.begin()+j);
                           }
                        
                               }
                }
        }
    
    sort(vec.begin(), vec.end());

    for(int x : vec)
        {
            cout << x << " ";
        }
    return 0;
}

 

배열의 원소를 삭제하고 싶을 때 erase() 함수를 사용하면된다

배열의 원소가 삭제됨과 동시에 크기도 줄어든다

 

이때문에 i와 j의 크기를 비교하여 erase() 부분을 처리 해준것이다

i가 j보다 작은데 i먼저 삭제하게 되면 배열의 길이가 줄어들기때문에

원하는 인덱스의 한 칸 뒤에 접근하게된다

 

그대로 구현을 해봤는데

틀렸다는 결과를 얻었다

 

문제를 잘 보니 가능한 정답이 여러가지인 경우 아무거나 출력한다 라는 말이 있었다

위의 코드는 어떤 케이스에서는 다섯 난쟁이가 되어버렸던 것이였다.

즉 가장 처음 조합이 생성되면 즉시 종료를 해도 된다는 의미로 생각했다

 

그래서 exit()함수를 사용해야겠다고 생각했다

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <stdlib.h>
using namespace std;

int main() {
    vector<int> vec;    
    
    for (int tmp=0; tmp<9; tmp++)
        {
            int value;
            cin >> value;
            vec.push_back(value);
            
            
        }
    
    int sum = accumulate(vec.begin(), vec.end(), 0);

    for (int i=0; i<9; i++)
        {
            for (int j=(i+1); j<9; j++)
                {
                    if (sum - (vec[i]+vec[j]) == 100) 
                        {
                           if (i < j)
                           {
                               vec.erase(vec.begin()+j);
                               vec.erase(vec.begin()+i);
                           }
                           else
                           {
                               vec.erase(vec.begin()+i);
                               vec.erase(vec.begin()+j);
                           }

                           sort(vec.begin(), vec.end());

                           for(int x : vec)
                            {
                                cout << x << " ";
                            }
                            exit(0);
                            
                        
                               }
                }
        }
    

    return 0;
}

 

정답이였다!