알고리즘 공부 - Day13

설하나·2022년 11월 17일
0

알고리즘

목록 보기
13/22

오늘의 알고리즘!!

1. 수의 표현

[문제 상황]

자연수 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를 넣어주었다.

profile
Backend

1개의 댓글

comment-user-thumbnail
2022년 11월 17일

이 글은 2021년 8월부터 12월까지 진행된 코딩테스트 대비 알고리즘 튜터링 알튜비튜의 회고글입니다. 코딩테스트 때문에 알고리즘 공부는 paper io 해야겠는데 ...

답글 달기