[SWEA 8275][C++] 햄스터(D4)

[문제보기]

 8275. 햄스터

SW Expert Academy

 

[풀이과정]

 햄스터의 우리가 최대 6개 각 우리에 최대 10마리가 들어갈 수 있다고 문제에 있으므로,

 최악의 경우 10^6 = 100만 테스트 케이스의 경우가 46이므로 4,600만이 최악의 경우의 수가 된다.

 그렇기 때문에 각 경우의 수를 하나씩 해봐도 시간 안에는 들어올 수 있으므로 DFS를 사용했다.

 

 (1) check()

      이 함수에서는 main()에서 저장한 기록들을 하나씩 가져와서 각 조건이 참인지 검사해보는 함수이다. 

 

 (2) dfs(int cage_idx, int sum)

      두번 째 for문부터 설명

        각 햄스터 cage에 0~x마리씩 넣어보는 부분이다.

      

      첫번째 if 문

        각 햄스터 cage에 0~x마리씩 넣어서 n번째 cage까지 왔을때 if문을 통해 check() 함수를 실행한다. 

        그리고 기록에 없는 cage에 대해서는 최대 햄스터 마리가 들어가기 때문에 sum_max를 사용하여 가장

        큰 값을 찾아낸다.

      

 (3) main()

      vector를 사용하여 기록에 대한 정보를 저장을 해준다. 이 정보는 check()함수에서 하나씩 불러와서 각 조건에 대해

      참, 거짓을 판단할 예정이다.      

 

[소스코드]

// 햄스터
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int n, x, m, sum_max;        // n: 햄스터 우리, x : 각 우리의 햄스터 수, m: 기록 수
int cage[7];
int ans[7];
vector<pair<pair<int, int>, int>> v;

bool check(){
    for(int i=0; i<v.size(); i++){
        int l = v[i].first.first;
        int r = v[i].first.second;
        int s = v[i].second;

        int temp = 0;
        for(int k =l; k<=r; k++){
            temp += cage[k];
        }

        if(temp != s){
            return false;
        }
    }
    return true;
}


void dfs(int cage_idx, int sum){
    if(cage_idx == n+1){
        if(check()){
            if(sum > sum_max){
                sum_max = sum;
                for(int i=1; i<=n; i++){
                    ans[i] = cage[i];
                }
            }
        }
        return;
    }

    for(int i=0; i<=x; i++){
        cage[cage_idx] = i;
        dfs(cage_idx+1, sum+i);
    }
}

int main(){
    cin.tie(0);
    cout.sync_with_stdio(false);

    int T;
    cin >> T;

    for(int test=1; test<=T; test++){
        memset(cage, 0, sizeof(cage));
        memset(ans, -1, sizeof(ans));
        v.clear();
        sum_max = -1;
        cin >> n >> x >> m;

        int l, r, s;
        for(int i=0; i<m; i++){
            cin >> l >> r >> s;
            v.push_back(make_pair(make_pair(l, r), s));
        }

        dfs(1, 0);

        bool flag = true;
        cout << "#" << test << " " ;
        for(int i=1; i<=n; i++){
            if(ans[i] == -1){
                cout << -1 ;
                flag = false;
                break;
            }
        }

        if(flag){
            for(int i=1; i<=n; i++){
                cout << ans[i] << " ";
            }
        }
        cout << "\n";
    }
}

 

[해결과정 중 실수한 부분]

 햄스터 문제는 3월에 문제를 보았던 기억이 난다.

 이때는 vector를 쓰는 법도 dfs를 쓰는 법도 몰랐기 때문에 칠판에 그림을 그리면서 문제를 풀어봤지만 결국에는 

 못 풀었었다. 하지만 이제는 다른 문제를 풀면서 dfs나 vector부분에 대해서 공부를 했기 때문에, 햄스터 문제를 다시 

 보자마자 dfs가 떠올랐고, 이 문제를 간단하게 풀 수가 있었다.