[백준/boj] 2309번: 일곱 난쟁이 | C++

 

 

 

문제 : https://www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

문제풀이 핵심

로직을 잘 짰는가..

나는 break 문의 조건을 이상하게 쓴 부분이랑 vector 에서 특정 인덱스 지우는 부분에서 헤맸다

---

 

 

문제풀이 코드

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

using namespace std;

vector<int> v(9);
int result;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    for(int i=0;i<9;i++) {
        cin >> v[i];
        result += v[i];
    }

    for(int i=0;i<8;i++){
        result -= v[i];

        for(int j=i+1; j<9;j++){ 
            result -= v[j];

            if(result == 100) {
                v.erase(v.begin()+i);
                v.erase(v.begin()+j-1);
                
                break;
            }
            
            result += v[j];
            
        }
        if(v.size() != 9) break;
        result += v[i];
    }

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

    for(int i=0; i<7; i++){
        cout << v[i]<<'\n';
    }

    return 0;
};

 

 

로직 설명

1. for 문 이용해 값을 입력받고, 입력 받은 값을 result에 바로바로 더해서 9개 값의 총합을 구해준다.

2. 총합에서 특정 두 개의 값들을 뺐을 때 100이 나오는 숫자 두개의 조합을 찾는다. (이중 for문 사용)

3. 해당 두개 값을 인덱스를 이용해서 vector.erase 해줘서 배열에서 삭제해준다

4. vector를 오름차순 정렬 해준다

5. 반복문으로 배열 순회하며 남아있는 값들을 출력해준다

 

if(v.size() != 9) break;

 

부분에서 원래는 조건을 result == 100 이라고 줘놓고 계속 뭐가 문제인지 몰라서 헤맸다

위의 코드를 보면 조건문에 들어오기 전에

result += v[j];

 

줄이 있기에 result 값이 다시 변경되는데 (9개 중 하나의 값만 빼준 상태가 됨)

이 부분을 인지를 못했었다.

 

추후에는 result 에서 2개의 값을 모두 빼준 후 result 가 100이 되었을때를 기준으로 v의 size 가 변경되었을테니 (9->7) 이 부분을 고려해서 조건문을 작성했다

---

 

 

문제풀이에 사용된 함수

사용된 개념들은 vector, vector.erase, vector sort 정도이고 나머지는 모두 구현이다

 

 

vector.erase()

vector에서 특정 인덱스를 삭제하는 방식이다. 

사용법 : 벡터변수명.erase(벡터변수명.begin()+삭제하고싶은 인덱스값);

 

벡터변수명.begin()를 통해 벡터의 주소가 들어가게 되어 해당 주소를 기준으로 값만 삭제할 수 있다.

이렇게 되면 삭제된 인덱스의 뒤에있는 값들이 모두 한칸 앞으로 당겨지게된다.

따라서 

v.erase(v.begin()+i);

v.erase(v.begin()+j-1);

처럼 erase 가 한번 되었으면 벡터가 재정렬되어 인덱스의 변동이 있게 된다. j가 i보다 무조건 크다는게 보장되어있는 상태이기에 벡터의 인덱스 j 값을 삭제하고 싶을 때, v.erase(v.begin()+j)라고 해주면 안되고 v.erase(v.begin()+j-1)을 해줘야 한다.

 

 

vector.sort()

vector에서 값을 오름차순 또는 내림차순으로 정렬하는 방식이다.

 

오름차순 정렬하기 (1,2,3)

사용법 : 변수명.sort(변수명.begin(),변수명.end())

 

내림차순 정렬하기 (3,2,1)

사용법 : 변수명.sort(변수명.rbegin(),변수명.rend())

 

erase 와 마찬가지로 begin과 end는 각각 벡터의 처음과 끝의 주소를 반환한다.

 

이는 배열에서 sort를 사용하는 방식과 달라보이는데 

그 이유는 배열의 이름은 배열의 첫번째 요소의 주소를 가지고 있기 때문이다 

 

+ ) 배열에서 sort 사용법 : 배열명.sort(배열명, 배열명+배열길이);

---

 

 

 

마무리

구현과 break 문의 조건 사용이 까다로운 문제였다

스터디 하면서 1시간동안 코드 짜고 뭐가 문제인지 고민했다

 

합이 100이 나오는 여러 경우가 있을 수 있다고 했는데 그 중 아무거나 출력하면 되니까 그냥 로직 돌면서 가장 먼저 나오는 경우가 출력되도록 했다. 따로 조건을 안걸어놨다는 이야기 ㅎ

 

다들 빠이팅