본인은 1의 개수와 2의 개수를 분리 시킨 다음에 이를 조합으로 생각했다.
1) 만약 1의 개수가 3개, 2의 개수가 5개라면 8개 중에 2가 들어갈 5개를 선택한다. 이 부분은 2가 들어가는 곳이라고 생각한다.
2) 이후로는 1 두개를 합쳐서 2 하나를 만들고, 이걸로 다시 조합에 넣었다.
-> ex) 1: 3개 / 2: 5개 = 8C5 => 1개 / 2: 6개 = 7C5
3) 결국, 1이 아예 1개, 0이 될때까지 이를 반복한다.
function combination(n, r){
var answer =1;
if(n===r){
return 1;
}
for(var i = n;i>(n-r);i--){
answer = answer * i;
}
for(var i =r;i>0;i--){
answer = answer /i;
}
return answer;
}
function solution(n) {
var answer = 0;
var one =n;
var two = 0;
while(true){
if(one===1||one===0){
answer+=combination(one+two,two);
break;
}
answer+=combination(one+two,two);
console.log(one,two,answer);
one = one -2;
two++;
}
return answer;
}
결과는 참담했다..... 내 풀이가 틀린건가??
이번엔 순열이 아니라 점화식을 이용했다. 문제를 1부터 차례대로 한 4까지 구해보니, 문제가 점화식에 대한 것이란걸 눈치챘다. 이를 알자마자 1분만에 문제를 풀었다.
이 부분을 아냐 모르냐가 이 문제에 핵심인 것 같다.
function solution(n) {
var ansArr = [0,1,2];
if(n<=2) return ansArr[n];
for(var i =3;i<=n;i++){
ansArr[i] = (ansArr[i-1] + ansArr[i-2])%1234567;
}
return ansArr[n];
}
헐 어려워보여요..