📑 문제 설명
Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.
1 + 2 + 3 + 4 + 5 = 15
4 + 5 + 6 = 15
7 + 8 = 15
15 = 15
자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.
🧑🏻💻 나의 풀이
class Solution {
public int solution(int n) {
int answer = 0;
for(int i=1;i<=n;i++) {
int sum = 0;
for(int j=i;j<=n;j++) {
sum += j;
if(sum==n) {
answer++;
break;
} else if(sum>n) {
break;
}
}
}
return answer;
}
}이중 for문을 사용해 i가 1일 때 j for문에서는 sum에 1+2+3+...+n이 담긴다.
sum==n이면 answer++, sum>n이면 탈출해 다음 i를 받는다.
🧑🏻💻 다른 사람의 풀이
public class Expressions {
public int expressions(int num) {
int answer = 0;
for (int i = 1; i <= num; i += 2)
if (num % i == 0)
answer++;
return answer;
}
} 홀수의 약수를 세는 방법이라고 하는데 이해가 잘 가지 않아 검색을 해봤다.
주어진 자연수를 연속된 수의 합으로 표현하는 방법의 수는 주어진 수의 홀수 약수의 개수와 같다는 정수론 정리가 있다고 한다.
문제에서 주어진 수인 15를 예시로 들자면
1. 약수 1: 15 = 15
2. 약수 3: 5+5+5 = 4+5+6 = 15
3. 약수 5: 5+5+5+5+5 = 1+2+3+4+5 = 15
4. 약수 15: 홀수 2n+1은 n+(n+1)의 합으로 표현할 수 있기 때문에 7+8 = 15
🔗 문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/12924
