[Baekjoon] 백준 N과 M 시리즈 1~4 (S3 / 순조부)

링크

https://www.acmicpc.net/workbook/view/2052

문제집: N과 M (시리즈)

www.acmicpc.net

공통 설명

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

입력
첫 번째 줄 : N M

출력
조건을 만족하는 수열을 출력
중복되는 수열을 여러 번 출력하면 안됨
수열은 공백으로 구분하여 출력

(1)

설명

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

해석
(1, 3) (3, 1)이 가능하므로,
순열

코드

const fs = require('fs');
const inputData = fs.readFileSync('/dev/stdin').toString().split(' ');
// const inputData = fs.readFileSync('example.txt').toString().split(' ');

// console.log(input);
var N = parseInt(inputData[0]);
var M = parseInt(inputData[1]);

var array = [];
var sel = [];
var v = [];

var answer = '';

for (var i = 0; i < N; i++) {
    array[i] = i + 1;
    v[i] = false;
}

for (var i = 0; i < M; i++) {
    sel[i] = 0;
}

recursive(0);

function recursive(count) {
    if (count == sel.length) {
        answer = '';

        for (var i = 0; i < sel.length; i++) {
            answer += sel[i];
            answer += ' ';
        }
        console.log(answer);
        return;
    }

    for (var i = 0; i < array.length; i++) {
        if (v[i] == true) continue;
        v[i] = true;
        sel[count] = array[i];
        recursive(count + 1);
        sel[count] = 0;
        v[i] = false;
    }
}

(2)

설명

1부터 N까지 자연수 중 중복 없이 M개를 고른 수열
고른 수열은 오름차순이어야 함

해석
(1, 3) (3, 1)이 불가능하므로,
조합

코드

const fs = require('fs');
const inputData = fs.readFileSync('/dev/stdin').toString().split(' ');
// const inputData = fs.readFileSync('example.txt').toString().split(' ');

var N = parseInt(inputData[0]);
var M = parseInt(inputData[1]);

var array = [];
var sel = [];
// var v = [];

var answer = '';

for (var i = 0; i < N; i++) {
    array[i] = i + 1;
    // v[i] = false;
}

for (var i = 0; i < M; i++) {
    sel[i] = 0;
}

recursive(0, 0);

function recursive(count, index) {
    if (count == sel.length) {
        answer = '';

        for (var i = 0; i < sel.length; i++) {
            answer += sel[i];
            answer += ' ';
        }
        console.log(answer);
        return;
    }

    for (var i = index; i < array.length; i++) {
        // if (v[i] == true) continue;
        // v[i] = true;
        sel[count] = array[i];
        recursive(count + 1, i + 1);
        sel[count] = 0;
        // v[i] = false;
    }
}

(3)

설명

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

해석
(1, 1, 3) (3, 1, 1)이 가능하므로,
중복순열

코드

const fs = require('fs');
const inputData = fs.readFileSync('/dev/stdin').toString().split(' ');
// const inputData = fs.readFileSync('example.txt').toString().split(' ');

// console.log(input);
var N = parseInt(inputData[0]);
var M = parseInt(inputData[1]);

var array = [];
var sel = [];
var v = [];

var answer = '';

for (var i = 0; i < N; i++) {
    array[i] = i + 1;
    v[i] = false;
}

for (var i = 0; i < M; i++) {
    sel[i] = 0;
}

recursive(0);
console.log(answer);

function recursive(count) {
    // answer = '';
    if (count == sel.length) {
        for (var i = 0; i < sel.length; i++) {
            answer += sel[i];
            answer += ' ';
        }
        answer += '\n';
        return;
    }

    for (var i = 0; i < array.length; i++) {
        // if (v[i] == true) continue;
        v[i] = true;
        sel[count] = array[i];
        recursive(count + 1);
        sel[count] = 0;
        v[i] = false;
    }
}

(4)

설명

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

해석
(1, 1, 3) (3, 1, 1)이 불가능하므로,
중복조합

코드

const fs = require('fs');
// const inputData = fs.readFileSync('/dev/stdin').toString().split(' ');
const inputData = fs.readFileSync('example.txt').toString().split(' ');

var N = parseInt(inputData[0]);
var M = parseInt(inputData[1]);

var array = [];
var sel = [];
// var v = [];

var answer = '';

for (var i = 0; i < N; i++) {
    array[i] = i + 1;
    // v[i] = false;
}

for (var i = 0; i < M; i++) {
    sel[i] = 0;
}

recursive(0, 0);
console.log(answer);


function recursive(count, index) {
    if (count == sel.length) {
        // answer = '';

        for (var i = 0; i < sel.length; i++) {
            answer += sel[i];
            answer += ' ';
        }
        answer += '\n';

        return;
    }

    for (var i = index; i < array.length; i++) {
        // if (v[i] == true) continue;
        // v[i] = true;
        sel[count] = array[i];
        recursive(count + 1, i);
        sel[count] = 0;
        // v[i] = false;
    }
}

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java