N과 M 시리즈

[Jinsun-Lee]

리드미

[Jinsun-Lee]

추가 풀이한 문제 (리드미에 없음)

N과 M 시리즈 전체

• N과 M (1)
• N과 M (2)
• N과 M (3)
• N과 M (4)
• N과 M (5)
• N과 M (6)
• N과 M (7)
• N과 M (8)
• N과 M (9)
• N과 M (10)
• N과 M (11)
• N과 M (12)

[Jinsun-Lee]

리뷰할 때

• N과 M: 백트래킹 구현 시 주의사항
• N과 M: next_permutation 구현 시 주의사항
• ⭐15649. N과 M (1)
• ⭐15650. N과 M (2)
• ⭐15651. N과 M (3)
• ⭐15652. N과 M (4)
• ⭐15663. N과 M (9)

[Jinsun-Lee]

N과 M: 백트래킹 구현 시 주의사항

• sort(num, num + N) 누락 주의
• 순열(1) → 중복순열(3) 주의

void logic_159(int depth) {
    if (depth >= M) { print(); return; }

    //int pre = 0; //⭐N개의 수에 중복이 있을 경우 = 9ABC
    for (int i = 0; i < N; ++i) {
        //if (visited[i]) continue; //⭐순서 매우 중요

        //if (pre == num[i]) continue; //9ABC
        //pre = num[i]; //9ABC

        visited[i] = true;
        ans[depth] = num[i];
        logic_159(depth + 1);
        visited[i] = 0;
    }
}

void logic_26A(int depth, int start) {
    if (depth >= M) { print(); return; }

    //int pre = 0; //A
    for (int i = start; i < N; ++i) {
        //if (pre == num[i]) continue; //A
        //pre = num[i]; //A

        ans[depth] = num[i];
        logic_26A(depth+1, i+1); //⭐start+1아니고 i+1이야
    }
}

[Jinsun-Lee]

N과 M: next_permutation 구현 시 주의사항

vector<bool> mask(N, 1); // 011 → 101 → 110
fill(mask.begin(), mask.begin() + M, 0);

do {
    if (mask[i]==0) 동작
} while (next_permutation(mask.begin(), mask.end())); // num이 아니지

[Jinsun-Lee]

2

// 10 시작시작+M if(!mask[i]) next
vector<bool> mask(N, 1);
fill(mask.begin(), mask.begin() + M, 0); //⭐

do {
    for (int i = 0; i < N; i++) if (mask[i] == 0) cout << i+1 << " ";
    cout << "\n";
} while (next_permutation(mask.begin(), mask.end()));

1

#include <vector>
#include <algorithm>

int main() {
    int N, M; cin >> N >> M;

    vector<bool> mask(N, 1); // 조합
    fill(mask.begin(), mask.begin()+M, 0);

    vector<vector<int>> ans; // 순열, 조합으로 순열을 만듦

    do {
        vector<int> combi; //⭐조합으로 만들어진 수
        for (int i = 0; i < N; ++i) if (!mask[i]) combi.push_back(i+1);
        do ans.push_back(combi);
        while (next_permutation(combi.begin(), combi.end()));
    } while (next_permutation(mask.begin(), mask.end()));

    sort(ans.begin(), ans.end()); // 순열 사전순 정렬
    for (auto& i : ans) {
        for (auto& j : i) cout << j << " ";
        cout << "\n";
    }
    return 0;
}

3

#include <vector>
#include <algorithm>

int main() {
    int N, M; cin >> N >> M;

    vector<bool> mask(N+M-1, 1); //⭐
    fill(mask.begin(), mask.end()-M, 0); //⭐

    vector<vector<int>> ans;
    do {
        vector<int> combi;
        for (int i = 0, t = 1; i < N+M-1; ++i) { //⭐
            if (mask[i]) combi.push_back(t); //⭐
            else ++t; //⭐
        }
        do ans.push_back(combi);
        while (next_permutation(combi.begin(), combi.end()));
    } while (next_permutation(mask.begin(), mask.end()));

    sort(ans.begin(), ans.end());
    for (auto& i : ans) {
        for (auto& j : i) cout << j << " ";
        cout << "\n";
    }
    return 0;
}

4

do {
    vector<int> combi;
    for (int i = 0, t = 1; i < N+M-1; ++i) {
        if (mask[i]) combi.push_back(t);
        else ++t; 
    }
    // do ans.push_back(combi);
    // while (next_permutation(combi.begin(), combi.end()));
    ans.push_back(combi); //⭐3번에서 M개의 수를 먼저 선택하는 것만 함
} while (next_permutation(mask.begin(), mask.end()));