728x90
😢 순열인지 조합인지 문제가 애매하지만, 결과를 보면 조합이다.
Keyword: '고른 수열은 오름차순이어야 한다'
😊 이 문제 역시 N과 M (1)과 마찬가지로 DFS로 해결이 가능하다.
N과 M (1)는 재귀를 위한 for loop에서 index를 항상 맨 처음부터 다시 돌았다면(모든 경우의 수를 위해),
이 문제에서는 지난 숫자는 제외하고 for loop을 진행한다(중복을 피하기 위해)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // N and M (2) Combination | |
| // For submit | |
| // const fs = require('fs'); | |
| // const input = fs.readFileSync('/dev/stdin').toString().trim().split(' ').map(nm => parseInt(nm)); | |
| // For local test | |
| // const input = [3, 1]; | |
| // const N = input.shift(); | |
| // const M = input.shift(); | |
| // const visited = new Array(N); | |
| // const output = []; | |
| // function dfs(idx, cnt) { | |
| // if (cnt === M) { | |
| // console.log(output.join(' ')); | |
| // return; | |
| // } | |
| // for (let i = idx; i < N; i++) { | |
| // if (visited[i] === true) continue; | |
| // visited[i] = true; | |
| // output.push(i + 1); | |
| // dfs(i, cnt + 1); | |
| // output.pop(); | |
| // visited[i] = false; | |
| // } | |
| // } | |
| // dfs(0, 0); | |
| // 2nd Solution | |
| // For submit | |
| // const fs = require('fs'); | |
| // const input = fs.readFileSync('/dev/stdin').toString().trim().split(' ').map(nm => parseInt(nm)); | |
| // For local test | |
| const input = [3, 1]; | |
| const N = input.shift(); | |
| const M = input.shift(); | |
| const visited = new Array(N); | |
| const output = []; | |
| let result = ''; | |
| function dfs(idx, cnt) { | |
| if (cnt === M) { | |
| result += `${output.join(' ')}\n`; | |
| return; | |
| } | |
| for (let i = idx; i < N; i++) { | |
| if (visited[i] === true) continue; | |
| visited[i] = true; | |
| output.push(i + 1); | |
| dfs(i, cnt + 1); | |
| output.pop(); | |
| visited[i] = false; | |
| } | |
| } | |
| dfs(0, 0); | |
| console.log(result); |
'Algorithm > JavaScript(Node.js)' 카테고리의 다른 글
| 백준 15652번: N과 M (4) Node.js(JavaScript) (0) | 2020.02.27 |
|---|---|
| 백준 15651번: N과 M (3) Node.js(JavaScript) (0) | 2020.02.25 |
| 백준 15649번: N과 M (1) Node.js(JavaScript) (0) | 2020.02.24 |
| 백준 10814: 나이순 정렬 Node.js(JavaScript) (0) | 2020.02.22 |
| 백준 1181번: 단어 정렬 Node.js(JavaScript) (0) | 2020.02.20 |