문제

숫자 1, 2, 3의 합을 이용하여 숫자 합 4를 갖는 모든 가지 수를 구해라

e.g

1+1+1+1
1+1+2
1+2+1
1+3
2+1+1
2+2
3+1

총 7개

해결 1

• 중복순열 사용
• • 숫자 합 4를 갖는 숫자 모음 중 가장 긴 배열 사용

    1+1+1+1 의 길이 4

function permutation(arr, selectNum) {
  let result = [];
  if (selectNum === 1) return arr.map((v) => [v]);

  arr.forEach((v, idx, arr) => {
    const fixer = v;
    const restArr = arr; // 순열과 다른 부분
    const permuationArr = permutation(restArr, selectNum - 1);
    const combineFixer = permuationArr.map((v) => [fixer, ...v]);
    result.push(...combineFixer);
  });
  return result;
}


function solution(n, arr){
	let result = 0;
  
  for(let i = 1; i < n+1; i++){
  	permutation(arr, i).forEach( index => {
    	const sum = index.reduce((pre, curr) => pre+curr, 0);
      if(sum === 4){
      	result += 1;
      }
    })
  }
  return result;
}


// 최대 길이 // 1+1+1+1
const n = 4
const arr =[1,2,3]
const result = solution(n, arr);

console.log(result)

해결 2

• dp 사용

F(n)이란 합 n을 갖는 가지수
F(1) = 1개 // 1
F(2) = 2개 // 1+1, 2
F(3) = 4개 // 1+1+1, 1+2, 2+1, 3
F(4) = 7개 // F(3)+F(2)+F(1)

• 점화식
  F(n) = F(n-1) + F(n-2) + F(n-3);

const F =[0, 1, 2, 4] // F 1, 2, 3을 넣어놈 F[0]은 생략


function solution(n){
	for(let i = 4; i <= n; i++){
    	F[i] = F[i-1] +F[i-2]+F[i-3];
    }
  
  return F[n];
}

const n = 4;
const result = solution(n)
console.log(result);

결론

• 해결 1 걸린 시간 :

0.33ms (2)
0.44ms (3)
0.72ms (4)
6.05ms (7)
110.61ms (10)

• 해결 2 걸린 시간 :

  0.209ms (4)
  0.19 ms (7)

• 해결 2의 경우 O(n)의 시간 복잡도를 갖음. (평균 0.2ms 를 왔다갔다)
• console.time을 이용한 시간을 재보았을 때 어느 경우에도
  해결 2의 시간보다 빠르게 동작하는 경우가 없음.