로또의 경우의 수를 출력해주면 되는 문제 0과 1을 이용해 조합을 만들고 역순으로 된 출력을 정방향으로 바꾸기 위해 벡터에 넣고 정렬해준다.

새로운 반복형식을 배운문제


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
 
int main()
{
    int input;
    cin >> input;
    while (input != 0)
    {
        vector<int> lotto;
        vector<int> check;
        for (int i = 0; i < input; ++i)
        {
            int x;
            cin >> x;
            lotto.push_back(x);
        }
        for (int i = 0; i < input - 6; ++i)
            check.push_back(0);
        for (int i = 0; i < 6; ++i)
            check.push_back(1);
 
        vector<vector<int>> ans;
        do
        {
            vector<int> temp_ans;
            for (int i = 0; i < input; ++i)
            {
                if (check[i] == 1)
                {
                    temp_ans.push_back(lotto[i]);
                }
            }
            ans.push_back(temp_ans);
        } while (next_permutation(check.begin(), check.end()));
        sort(ans.begin(), ans.end());
        for (auto &v : ans)
        {
            for (int i = 0; i < v.size(); ++i)
            {
                cout << v[i] << " ";
            }
            cout << endl;
        }
        cin >> input;
        cout << endl;
    }
    
    return 0;
}
cs


저작자표시 비영리 (새창열림)

'백준 온라인 저지' 카테고리의 다른 글

백준 14889: 스타트와 링크  (0) 2018.07.18
백준 14888: 연산자 끼워넣기  (0) 2018.07.18
백준 10971: 외판원 순회2  (0) 2018.07.17
백준 2529: 부등호  (0) 2018.07.17
백준 10819: 차이를 최대로  (0) 2018.07.17

순열을 이용해서 순회를 구하는 문제 조건에서 마을은 10미만이니 팩토리얼의 경우의 수를 이용해서 풀어 볼 수 있다. 시간 복잡도는 크게나오지만 단순하다. 마을 사이의 이동이 불가능한 경우는 불리언 변수로 제외시켜준다. 끝마을에서 처음마을로 갈 때는 똑같은 for문에 넣어주면 초과되니 따로 빼준다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> dis(12);
vector<int> town;
int main()
{
    int input;
    cin >> input;
    for (int i = 0; i < input; ++i)
    for (int j = 0; j < input; ++j)
    {
        int temp;
        cin >> temp;
        dis[i].push_back(temp);
    }
    for (int i = 0; i < input; ++i)
        town.push_back(i);
    //순열에 따라 갈 수 있는지 여부를 판단한 후 거리를 구한다.
    int ans = 2147483647;
    do
    {
        int sum = 0;
        bool ok = true;
        for (int i = 0; i < input - 1; ++i)
        {
            if (dis[town[i]][town[i + 1]] == 0)
                ok = false;
            else
                sum += dis[town[i]][town[i + 1]];
        }
        
        if (ok && dis[town[input - 1]][town[0]] != 0)
        {
            sum += dis[town[input - 1]][town[0]];
            ans = min(ans, sum);
        }
    } while (next_permutation(town.begin(), town.end()));
    cout << ans << endl;
    return 0;
}
cs


저작자표시 비영리 (새창열림)

'백준 온라인 저지' 카테고리의 다른 글

백준 14888: 연산자 끼워넣기  (0) 2018.07.18
백준 6603: 로또  (0) 2018.07.18
백준 2529: 부등호  (0) 2018.07.17
백준 10819: 차이를 최대로  (0) 2018.07.17
백준 10974: 모든 순열  (0) 2018.07.17

순열을 이용해서 모든 경우의 수를 대입해보는 문제 팩토리얼은 시간복잡도가 크지만 문제의 조건이 10미만이니 사용할만하다. 

코드는 내가 짠 것은 너무 더러워서 강의 슬라이드를 보고 리팩토링했는데.. 거의 똑같다


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool check(vector<char> & _sign, vector<int> & num)
{
    for (int i = 0; i < _sign.size(); ++i)
    {
        if (_sign[i] == '>' && num[i] < num[i + 1])
            return false;
        if (_sign[i] == '<' && num[i] > num[i + 1])
            return false;
    }
    return true;
}
 
int main()
{
    vector<char> sign;
    vector<int> num_max;
    vector<int> num_min;
    int input;
    cin >> input;
    for (int i = 0; i < input; ++i)
    {
        char t_input;
        cin >> t_input;
        sign.push_back(t_input);
    }
    //부등호 갯수의 맞게 최댓값들을 넣어줌
    for (int i = 9; i >= 9 - input; --i)
        num_max.push_back(i);
    for (int i = 0; i <= input; ++i)
        num_min.push_back(i);
    do
    {
        if (check(sign, num_max))
            break;
    } while (prev_permutation(num_max.begin(), num_max.end()));
    do
    {
        if (check(sign, num_min))
            break;
    } while (next_permutation(num_min.begin(), num_min.end()));
 
    for (int i = 0; i < num_max.size(); ++i)
        cout << num_max[i];
    cout << endl;
    for (int i = 0; i < num_min.size(); ++i)
        cout << num_min[i];
    cout << endl;
    return 0;
}
cs


저작자표시 비영리 (새창열림)

'백준 온라인 저지' 카테고리의 다른 글

백준 6603: 로또  (0) 2018.07.18
백준 10971: 외판원 순회2  (0) 2018.07.17
백준 10819: 차이를 최대로  (0) 2018.07.17
백준 10974: 모든 순열  (0) 2018.07.17
백준 10973: 이전 순열  (0) 2018.07.17

+ Recent posts

티스토리툴바