문제
1부터N까지번호가적힌구슬이있습니다.이중 M개를뽑는방법의수를출력하는프로그 램을 작성하세요.
[입력설명]
첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.
[출력설명]
첫 번째 줄에 결과를 출력합니다. 맨 마지막 총 경우의 수를 출력합니다. 출력순서는 사전순으로 오름차순으로 출력합니다.
입력예제 1
4 2 (4C2라는 뜻)
출력예제 1
1 2
1 3
1 4
2 3
2 4
3 4
6
문제 풀이
코드
중복을 허용하지 않는 문제이다. 즉, 뽑았던 수는 뽑으면 안되기 때문에 let i=s와 같이 작성한다.
앞선 문제에서도 살펴봤듯이, tmp.slice()를 통해 깊은 복사를 해주어야한다. 하지 않으면 얕은복사가 되어 push했던 값들도 함께 변화한다.
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(n, m){
let answer=[];
let tmp=Array.from({length:m}, ()=>0);
function DFS(L, s){
if(L===m){
answer.push(tmp.slice()); //깊은 복사되어서 들어감
}
else{
for(let i=s; i<=n; i++){
tmp[L]=i; //L지점에서 i를 뽑았다는 기록
DFS(L+1, i+1);
}
}
}
DFS(0, 1);
return answer;
}
console.log(solution(4, 2));
</script>
</body>
</html>
내가 짱이다 😎 매일 조금씩 성장하기🌱
9/17
조합의 경우! 잘 입력해두기
순열과 조합은 다르다. 순열은 {1, 2}, {2, 1}을 다르다고 보지만 조합은 이 두개를 같은 것으로 보기때문에 하나로 친다.
순열은 ch를 사용해서 풀이하지만, 조합은 ch로 풀이하지 않는다.
공식 참고
https://coding-factory.tistory.com/606