문제

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

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

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

문제풀이

이번 문제는 N과M(2)의 응용버전으로 보인다.
문제 조건을 정리하면 다음과 같다.

1. 중복 가능 (1 1 1, 2 2 2 등)
2. arr[lastIdx] <= i (1 1 2 가능, 1 2 1 불가능)

즉, 중복이 가능하지만 오름차순으로 정렬되어야 한다.
그래서 재귀함수로 진입하는 조건을 이렇게 바꿨다.
결과는 바로 통과!

/* arr 마지막 요소가 i 이하거나 arr이 빈 배열일 떄 */
if( arr[arr.length-1] <= i || arr.length === 0) {

아래는 전체코드다.

//init용
const stdin: string[] = (process.platform ==='linux'
? require('fs').readFileSync(0, 'utf-8')
: `
3 3
`).trim().split('\n');

const input = (()=>{
    let line = 0;
    return ()=> stdin[line++].split(" ").map( v => +v);
})();

const [N, M] = input();
//const result: number[][] = [];
let result = '';

const sol = (arr: number[]) => {
    if (arr.length === M){
        result += arr.join(" ");
        result += "\n";
      	
        return;
    }
        
    for (let i=1; i<=N; i++) {
        if( arr[arr.length-1] <= i || arr.length === 0) {
            sol([...arr, i]);
        }
    }
}

sol([]);
console.log(result);