[BOJ] 2309번 "일곱 난쟁이" (C++/Swift)

2309번 일곱 난쟁이

 

그냥 9개의 숫자 중, 합이 100이 되는 7개의 숫자를 찾으라는 것이다.

(스페셜 저지는 문제의 정답 조건을 만족하는 것들 중 아무거나 출력하는 문제임)

 

그냥 단순하게, 난쟁이가 겹치지 않게 (한 사람 두 번 세지 않도록)

정답 조건(7명이며, 키의 합이 100일 것)을 확인하는 재귀함수 돌렸다.

for문 7개 쓸 순 없으니까.. ^^ (for문 7개 써도 된다,, 당연히 결과는 같음!!)

 

C++

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int height[9];
vector<int> answer;

void solve(int next_index, int count, int sum, vector<int> list) {
    if(count==7 && sum==100) {
        answer = list;
        return;
    }
    if(count>7 || sum>100) return;

    for(int i=next_index; i < 9; i++){
        list.push_back(height[i]);
        solve(i+1,count+1, sum+height[i],list);
        list.pop_back();
    }
}

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

    for(int i=0; i<9; i++) {
        cin >> height[i];
    }
    vector<int> v;
    solve(0,0,0,v);
    sort(answer.begin(), answer.end());
    for(auto i : answer){
        cout<<i<<"\n";
    }
}

Swift

import Foundation

var height: [Int] = []
var answer: [Int] = []

func solve(nextIndex: Int, count: Int, sum: Int, list: [Int]){
    if count > 7 || sum > 100 { return }
    if count == 7 && sum == 100 {
        answer = list
        return
    }
    var newList = list
    for i in nextIndex..<9 {
        newList.append(height[i])
        solve(nextIndex: i+1, count: count+1, sum: sum+height[i], list: newList)
        newList.removeLast()
    }
}

func main() {
    for _ in 0..<9 {
        height.append(Int(readLine()!)!)
    }
    solve(nextIndex: 0, count: 0, sum: 0, list: [0])
    answer.sort();
    for i in 1...7 {
        print(answer[i])
    }
}

main()

 

 

 

근데 지금 갑자기 궁금해서 7개의 for문을 써봤다.. Swift로..

괄호만리장성

import Foundation

var height: [Int] = []
var answer: [Int] = []

func solve(nextIndex: Int, count: Int, sum: Int, list: [Int]){
    if count > 7 || sum > 100 { return }
    if count == 7 && sum == 100 {
        answer = list
        return
    }
    var newList = list
    for i in nextIndex..<9 {
        newList.append(height[i])
        solve(nextIndex: i+1, count: count+1, sum: sum+height[i], list: newList)
        newList.removeLast()
    }
}

func main() {
    for _ in 0..<9 {
        height.append(Int(readLine()!)!)
    }
    for i in 0...2 {
        for q in i+1...3{
            for w in q+1...4 {
                for e in w+1...5 {
                    for r in e+1...6 {
                        for t in r+1...7 {
                            for y in t+1...8 {
                                if height[i] + height[q] + height[w] + height[e] + height[r] + height[t] + height[y] == 100 {
                                    answer.append(contentsOf: [height[i], height[q], height[w], height[e], height[r], height[t], height[y]])
                                    
                                    answer.sort();
                                    for i in 0..<7 {
                                        print(answer[i])
                                    }
                                    return
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

main()