[BOJ - 18429] 근손실 (C++)

문제

 

접근방법

• 삼대 500은 항상 넘겨야 함 -> 백트래킹으로 조건에 맞춰서 접근하는 방법으로 구현하기로 결정
  • 모든 조건을 충족했을 때, N 만큼 진행이 되었을 것이므로 count 변수를 선언 -> N일 때 경우의 수를 증가

 

코드

#include <iostream>
#include <vector>

using namespace std;

int N, K;
vector<int> add_muscle;
vector<bool> visited;
int available_result = 0;

void dfs(int muscle, int cnt) {
    if (cnt == N) {
        available_result++;
        return;
    }

    for (int i = 0; i < N; i++) {
        if (!visited[i]) {
            int tmp_muscle = muscle + add_muscle[i] - K;
            if (tmp_muscle >= 500) {
                visited[i] = true;
                dfs(tmp_muscle, cnt + 1);
            }
            visited[i] = false;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> K;

    add_muscle.resize(N);
    visited.assign(N, false);

    for (int i = 0; i < N; i++) {
        cin >> add_muscle[i];
    }

    dfs(500, 0);
    cout << available_result << "\n";

    return 0;
}

 

리팩토링(?)

for (int i = 0; i < N; i++) {
    if (!visited[i]) {
        int tmp_muscle = muscle + add_muscle[i] - K;
        if (tmp_muscle >= 500) {
            visited[i] = true;
            dfs(tmp_muscle, cnt + 1);
        }
        visited[i] = false;
    }
}

• DFS 함수 내부의 반복문에서 visited를 처리하는 부분이 가독성이 떨어지는 문제

for (int i = 0; i < N; i++) {
    if (visited[i])
        continue;

    int new_muscle = muscle + add_muscle[i] - K;
    if (new_muscle < 500)
        continue;

    visited[i] = true;
    dfs(new_muscle, cnt + 1);
    visited[i] = false;
}

• continue 문으로 불필요한 중첩을 피하고 조건문을 연달하 사용 -> 가독성을 높임

 실제로 메모리가 줄어들거나 속도가 빨라지지는(애초에 0ms라 정확한 측정은 안되는데) 않은거 같기도,,, 근데 코드가 좀 이뻐지긴 했네용

 

링크

18429번: 근손실