- 알고리즘/개인공부
연속된 자연수의 합구하기 [투포인터] / 백준 2018
더모어더베러
2024. 6. 19. 22:38
문제
https://www.acmicpc.net/problem/2018
풀이
우선 문제에 주어진 시간 제한은 2초입니다. 이런 상황에서 O( nlogn ) 의 시간 복잡도 알고리즘을 사용하면 제한시간을 초과하므로 O( n )의 시간복잡도 알고리즘을 사용해야 합니다. 이런 경우 자주 사용하는 방법이 투포인터 입니다.
※ O ( n ) : 주어진 데이터 크기 n 만큼 연산횟수가 필요한 시간복잡도
연속된 자연수의 합을 구하는 것이 문제이므로 시작 인덱스와 종료 인덱스를 지정하여 연속된 수를 표현 하겠습니다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class 연속된자연수의합_투포인터_2018 {
public static void main(String[] args) {
try {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int count = 1;
int start_index = 1;
int end_index = 1;
int sum = 1;
while (end_index != N) { // end_index가 N이 되는 순간 while 반복문이 끝나서 자기 자신인 숫자일때의 count++를 할수 없으니 count에 미리 1을 넣어줬음
if (sum == N) {
count++;
end_index++;
sum = sum + end_index;
} else if (sum > N) {
sum = sum - start_index; // sum이 N 값을 넘어 버렸으니까 왼쪽 인덱스를 오른쪽으로 한칸 옮기면서 start_index값을 빼준다
start_index++;
} else if (sum < N) {
end_index++;
sum = sum + end_index;
}
}
bw.write(count+"");
bw.flush();
bw.close();
} catch (Exception e) {
e.printStackTrace();
}
}
}
출처