[JAVA] 27. 연속된 자연수의 합
2021. 10. 22. 22:58
728x90
설명
N입력으로 양의 정수 N이 입력되면 2개 이상의 연속된 자연수의 합으로 정수 N을 표현하는 방법의 가짓수를 출력하는 프로그램을 작성하세요.
만약 N=15이면
7+8=15
4+5+6=15
1+2+3+4+5=15
와 같이 총 3가지의 경우가 존재한다.
입력
첫 번째 줄에 양의 정수 N(7<=N<1000)이 주어집니다.
출력
첫 줄에 총 경우수를 출력합니다.
예시 입력 1
15
예시 출력 1
3
내 풀이
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int n = in.nextInt();
int pi=1, pj=2, sum = 1, answer =0;
while(pj <n){
sum += pj;
if(sum == n){
answer ++;
pj++;
}else{
while(sum>=n){
sum-=pi;
pi++;
if(sum==n){
answer++;
}
}
pj++;
}
}
System.out.println(answer);
}
}
다른 풀이
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int n = in.nextInt();
int m = n/2+1;
int pi=1, pj=2, sum = 1, answer =0;
while(pj <=m){
sum += pj;
if(sum == n){
answer ++;
pj++;
}else{
while(sum>=n){
sum-=pi;
pi++;
if(sum==n){
answer++;
}
}
pj++;
}
}
System.out.println(answer);
}
}
수학적 풀이
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int n = in.nextInt();
int cnt=1, answer =0;
// n을 m개의 자연수합으로 표현할 때, 1부터 m까지의 수를 n에서 빼고
// n을 m으로 나눴을 때 0이면 n은 m개의 자연수 합으로 나타낼 수 있다.
n--;
while(n>0){
cnt++;
n-=cnt;
if(n%cnt == 0){
answer++;
}
}
System.out.println(answer);
}
}
728x90
'알고리즘 > JAVA' 카테고리의 다른 글
[JAVA] 29. 학급회장 (0) | 2021.10.23 |
---|---|
[JAVA] 28. 최대 길이 연속부분수열 ✔ (0) | 2021.10.23 |
[JAVA] 26. 연속 부분 수열 ✔ (0) | 2021.10.22 |
[JAVA] 25. 최대 매출(Sliding Window) (0) | 2021.10.22 |
[JAVA] 23. 공통원소 구하기 - 복습! (0) | 2021.10.22 |