0️⃣ 문제 링크
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
1️⃣ 문제 설명
자연수 n이 주어졌을 때, 연속된 자연수들을 더하여 n을 만들 수 있는 경우의 수를 구하는 문제이다.
예를 들어 n = 15라면, 총 4가지가 된다.
- 1 + 2 + 3 + 4 + 5
- 4 + 5 + 6
- 7 + 8
- 15
2️⃣ 문제 접근 방식
- 연속된 자연수 구간이므로 투 포인터 이용
- 구간합이 n보다 작으면, end 증가
- 구간합이 n보다 크면, start 증가
- 구간합이 n이면, 경우의 수 증가 및 start 증가
k개의 연속된 수의 합 공식 활용
\[n = a + (a + 1) + ⋯ + (a + k − 1) = ka + {k(k - 1) \over 2}\]- answer를 1로 초기화
- n 자체를 자기 자신으로 표현하는 경우
- start가 n/2 이하까지 반복
- n/2를 초과하면 n이 나올 수 없는 경우 뿐임
시간 복잡도 : O(N)
3️⃣ 전체 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int solution(int n) {
int answer = 1;
int s = 1, e = 2;
while (s < e && s <= n/2) {
int k = e - s + 1;
int sum = (k * s) + (k * (k - 1)) / 2;
if (sum == n) {
answer++;
s++;
} else if (sum < n) {
e++;
} else {
s++;
}
}
return answer;
}
}
4️⃣ 다른 풀이
방법 1
- 투 포인터와 누적합 이용 → 연산량이 매우 적음
- 시간 복잡도 : O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public int solution(int n) {
int answer = 0;
int start = 1, end = 1;
int sum = 1;
while (start <= n) {
if (sum == n) {
answer++;
sum -= start;
start++;
}
else if (sum < n) {
end++;
sum += end;
}
else {
sum -= start;
start++;
}
if (end > n) break;
}
return answer;
}
}
방법 2
- 연속된 자연수로 표현되는 경우의 수 = 홀수 약수의 개수 라는 수학 정리 이용
- 시간 복잡도 : O(√n)
1
2
3
4
5
6
7
8
9
10
class Solution {
public int solution(int n) {
int answer = 0;
for (int i = 1; i <= n; i += 2)
if (n % i == 0)
answer++;
return answer;
}
}
방법 3
- 완전 탐색 이용(브루트포스)
- 모든 시작점 i에 대해 가능한 j까지의 합을 누적해 확인
- 시간 복잡도 : O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int solution(int n) {
int answer = 0;
for(int i = 1; i <= n; i++) {
int temp = 0;
for(int j = i; j <= n; j++) {
temp += j;
if (temp == n) {
answer++;
break;
} else if (temp > n) {
break;
}
}
}
return answer;
}
}
5️⃣ 회고 및 배운점
등차수열의 합 공식을 알게되었다. 평균 X 개수 = (첫항 + 끝항)/2 * k
등차수열 대신 누적합을 사용하면 계산량이 줄어들고 가독성이 좋아지는 것 같다.
연속된 자연수로 표현되는 경우의 수가 홀수 약수의 개수라는 성질을 깨닫게 되었다…