[CodingTest] 연속된 자연수의 합

 

📝 프로그래머스 코딩 Lv2. 숫자의 표현의 문제를 접한 내용 및 인프런의 강좌인 ' [인프런] 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비'를 수강하고 나서, 개인적으로 기록하고 싶은 내용을 기록한 글입니다. 인프런 강의를 수강하다가 접한 문제이며, 프로그래머스에 비슷한 문제가 있기에 글로 작성하여 내용을 기억하려고 합니다! 자세한 내용은 해당 문제 또는 해당 강의를 꼭꼭 참고해주세요 📖

 

public int solution(int n) {
        int answer = 0, cnt = 0;
        while(n > 0) {
            cnt++;
            n -= cnt;
            if(n%cnt == 0) answer++;
        }
        return answer;
}

 

 

예시로 n이라는 숫자가 존재하고, cnt라는 연속된 자연수의 개수가 존재한다고 가정해보자.

 

n = (a+1) + (a+2) + ... + (a+k)
n = k*a + (1 + 2 + ... + k)

 

여기서 자세히 알기 위해 20이라는 숫자로 가정해보자 (강의나 문제에서는 15로 가정한다, 자세한 내용은 강의 또는 문제 참고!)

cnt	n	if(n&cnt) == 0	answer	해당하는 부분
1	19	Okay	1	20
2	17	No	1
3	14	No	1
4	10	No	1
5	5	Okay	2	2 + 3 + 4 + 5 + 6

 

여기서 왜 n에서 cnt를 자꾸 빼주는지 궁금했다. 

 

예를 들어, a라는 숫자가 있는데 (a+1) + (a+2) + (a+3) 이라고 가정해보면, n = 3*a + 6 이 될 수 있다.

 

여기서 while문을 통해 n에서 cnt 가 각각 1,2,3일 때 n에서 해당 cnt들을 빼게 된다.

 

그러면 n은 이미 n - 6 인 상태가 되는데, 여기서 cnt 의 값은 cnt++(3번 반복중) 의 연산으로 3이 되어 있을 것이다.

 

그래서 위에서 말한 n = 3*a + 6 은 n -6 = 3*a 가 되어 있을 것이고 (n-6)/3 을 하여 a를 찾아주게 된다면

 

역으로 a+1, a+2, a+3을 찾을 수 있게 된다.

 

중요한 점은 (n-6)/3 에서 나머지가 0이 되어야 a를 찾을 수 있게 되며, 0이 아닌 경우 a는 자연수가 아니기에 연속된 자연수들을 찾을 수 없게 된다.

 

 

References

1. 프로그래머스 - 숫자의 표현 문제(Lv2)

프로그래머스

2. [인프런] 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

 

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런

3. 연속된 자연수의 합 2 (수학적풀이)

연속된 자연수의 합 2 (수학적풀이)