[BaekJoon] 1261 알고스팟 :: monton

코드

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

풀이

모든 경우의 수를 판단하는 문제이므로 dfs 사용

오름 차순으로 출력해야 하므로 algorithm 라이브러리에 있는 sort 함수를 사용하여 정렬해주었다

그후 visit 배열로 순차적으로 확인하고 7를 방문했을때 방문한 노드들의 합이 100인지 확인하고

100이면 출력하고 프로그램을 끝낸다

그게 아니라면 반환하여 계속 탐색한다

기본적인 dfs 문제로 1759번 암호 만들기 (https://www.acmicpc.net/problem/1759)와 유사한 문제이다

코드

#include <iostream>
#include<algorithm>
using namespace std;
 
int arr[10], visit[10];
 
void func(int x, int cnt) {
    if (cnt == 7) {
        int num = 0;
        for (int i = 0; i < 9; i++) {
            if (visit[i]) num += arr[i];
        }
 
        if (num == 100) {
            for (int i = 0; i < 9; i++) 
                if (visit[i]) cout << arr[i]<<endl;
            exit(0);
        }
        else return;
    }
 
    for (int i = x; i < 9; i++) {
        if (!visit[i]) {
            visit[i] = 1;
            func(i, cnt + 1);
            visit[i] = 0;
        }
    }
}
 
int main() {
    for (int i = 0; i < 9; i++) cin >> arr[i];
    sort(arr, arr + 9);
    func(0, 0);
}