[BOJ 15649~15652번/C++] N과 M

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

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

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

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

N과 M

풀이

4개의 문제는 모두 고등학교 수학 시간에 배워봤을 순열과 조합을 구현하는 문제였다.

순열과 조합은 백트래킹 문제에서 많이 사용되므로 꼭 숙지해야한다.

 

[15649번]

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

 

즉, \(_{N}\mathrm{P}_{M}\)을 구현하라는 소리이다.

 

#include <cstdio>

int num[9];
bool visited[9];
int N, M;

void dfs(int count) {
    if (count == M) {
        for (int i = 0; i < M; i++) {
            printf("%d ", num[i]);
        }
        printf("\n");
    }

    for (int i = 1; i <= N; i++) {
        if (!visited[i]) {
            visited[i] = true;
            num[count] = i;
            dfs(count + 1);
            visited[i] = false;
        }
    }
}

int main() {
    for (int i = 0; i < 9; i++) {
        num[i] = i;
    }

    scanf("%d %d", &N, &M);

    dfs(0);

    return 0;
}

 

---

 

[15650번]

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

 

즉, \(_{N}\mathrm{C}_{M}\)을 구현하라는 소리이다.

 

#include <cstdio>

int num[9];
bool visited[9];
int N, M;

void dfs(int count, int n) {
    if (count == M) {
        for (int i = 0; i < M; i++) {
            printf("%d ", num[i]);
        }
        printf("\n");
    }

    for (int i = n; i <= N; i++) {
        if (!visited[i]) {
            visited[i] = true;
            num[count] = i;
            dfs(count + 1, i);
            visited[i] = false;
        }
    }
}

int main() {
    for (int i = 0; i < 9; i++) {
        num[i] = i;
    }

    scanf("%d %d", &N, &M);

    dfs(0, 1);

    return 0;
}

 

---

 

[15651번]

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

 

즉, \(_{N}\mathrm{Pi}_{M}\)을 구현하라는 소리이다.

 

#include <cstdio>

int num[9];
int N, M;

void dfs(int count) {
    if (count == M) {
        for (int i = 0; i < M; i++) {
            printf("%d ", num[i]);
        }
        printf("\n");
        return;
    }

    for (int i = 1; i <= N; i++) {
        num[count] = i;
        dfs(count + 1);
    }
}

int main() {
    for (int i = 0; i < 9; i++) {
        num[i] = i;
    }

    scanf("%d %d", &N, &M);

    dfs(0);

    return 0;
}

 

---

 

[15652번]

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

 

즉, \(_{N}\mathrm{H}_{M}\)을 구현하라는 소리이다.

 

#include <cstdio>

int num[9];
int N, M;

void dfs(int count, int n) {
    if (count == M) {
        for (int i = 0; i < M; i++) {
            printf("%d ", num[i]);
        }
        printf("\n");
        return;
    }

    for (int i = n; i <= N; i++) {
        num[count] = i;
        dfs(count + 1, i);
    }
}

int main() {
    for (int i = 0; i < 9; i++) {
        num[i] = i;
    }

    scanf("%d %d", &N, &M);

    dfs(0, 1);

    return 0;
}