오늘의 알고리즘!!
자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개이다.
예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.
1 + 2 + 3 + 4 + 5 = 15
4 + 5 + 6 = 15
7 + 8 = 15
15 = 15
자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성하는 문제였다.
알고리즘 7일차에 중첩 for()문을 이용해서 풀었었지만, n의 값이 커지면서 효율성 측면에서 통과를 실패하였던 문제였다.
function solution(n) {
let count = 0;
for ( let i = 1 ; i < n/2 + 1 ; i++ ){
// 1부터 i항까지의 합 sum
const sum = i * (i + 1) / 2;
// n에서 sum을 뺀 수는 다시 i의 배수가 되어야 한다.
const sub = n - sum;
if(sub < 0) break;
if(sub % i === 0){
count++;
}
}
return count;
}
만약, 주어진 수 n에 대해서 시작 수가 a이고 총 갯수가 m인 경우에 식을 만들어보면 아래와 같다.
{a+(a+m-1)}*m/2 = n
좌항을 풀어보자
(2a+m-1)*m/2 = n
(m^2+2am-m)/2 = n
{(m^2+m)+(2am-2m)}/2 = n
{m(m+1)+2m(a-1)}/2 = n
m(m+1)/2+m(a-1)=n
여기서 m은 총 갯수를 의미하는 문자이기 때문에 m(m+1)/2는 a부터 m까지 연속된 수의 총합을 의미한다.
(이해가 되지 않는다면 등차수열의 합에 대한 링크를 걸어 놓으니 참고 바란다.)
좌항의 m(m+1)/2를 우항으로 이항한 후 식을 정리한다면 아래와 같다.
m(a-1) = n - m(m+1)/2
//보기 쉽게 한글로 쓰자면
m(a-1) = n - [a부터 m까지 연속된 수의 총합]
즉, 전체 수에서 총합을 빼개된다면 그 수는 총 개수 m의 배수가 된다는 것이 였다. 이를 이용해서 조건문을 구성하였고
이때 음수가 나올 수 있으므로 조건문인 if()문을 사용해서 break를 넣어주었다.
이 글은 2021년 8월부터 12월까지 진행된 코딩테스트 대비 알고리즘 튜터링 알튜비튜의 회고글입니다. 코딩테스트 때문에 알고리즘 공부는 paper io 해야겠는데 ...