방명록
- [백준 / 자바] 2018번 수들의 합 5 - 투 포인터2023년 12월 19일 00시 37분 28초에 업로드 된 글입니다.작성자: 민발자728x90
2018번: 수들의 합 5
어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한
www.acmicpc.net
문제
어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.
예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.
N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.
입력
첫 줄에 정수 N이 주어진다.
출력
입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오
풀이
시간 제한이 2초, n의 최댓값이 10,000,000으로 매우 큼
O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한 시간 초과
O(n)의 시간 복잡도 알고리즘을 사용해야함
→ 투 포인터 알고리즘 사용
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int count = 1; // 가지 수 카운트 int s = 1; // startIdx int e = 1; // endIdx int sum = 1; // 합계 while (e != n) { if(sum == n) { count++; e++; sum = sum + e; } else if (sum > n) { sum = sum - s; s++; } else { e++; sum = sum + e; } } System.out.println(count);
728x90'기록 > 백준' 카테고리의 다른 글
[백준 / 자바] 2164번 카드2 - 큐 (0) 2023.12.19 [백준 / 자바] 1874번 스택 수열 - 스택 (0) 2023.12.19 [백준 / 자바] 11659번 구간 합 구하기 4 - 구간 합 (0) 2023.12.18 [백준 / 자바] 24267번 알고리즘 수업 - 알고리즘의 수행 시간6 (0) 2023.12.18 [백준 / 자바] 24266번 알고리즘 수업 - 알고리즘의 수행 시간5 (0) 2023.12.17 다음글이 없습니다.이전글이 없습니다.댓글