https://www.acmicpc.net/problem/2018
2018번: 수들의 합 5
어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한
www.acmicpc.net
기초적인 투포인터 문제다.
풀이
1부터 N까지의 수를 오름차순으로 담은 배열을 생성한 뒤, 인덱스를 활용한 구간탐색을 통해 답을 구하면 된다. 시작 인덱스와 끝인덱스는 동일하게 0으로 시작한 뒤, 아래와 같은 조건으로 반복을 수행한다.
- 누적합이 목표 숫자보다 크다면 시작 인덱스가 가리키는 숫자를 뺀 뒤 시작 인덱스 증가
- 누적합이 목표 숫자보다 작거나 같다면 끝 인덱스가 가리키는 숫자를 더 해준 뒤 끝 인덱스 증가
- 누적합이 목표숫자와 같다면 카운트 증가
- 끝 인덱스가 증가할 부분이 없다면 종료
| 연속된 수 | 합 | 행동 |
| (없음) | 0 | +1 |
| 1 | 1 | +2 |
| 1+2 | 3 | +3 |
| 1+2+3 | 6 | +4 |
| 1+2+3+4 | 10 | -1 |
| 2+3+4 | 9 | -2 |
| 3+4 | 7 | +5, cnt++ |
| 3+4+5 | 12 | -3 |
| 4+5 | 9 | -4 |
| 5 | 5 | +6 |
| 5+6 | 11 | -5 |
| 6 | 6 | +7 |
| 6+7 | 13 | -6 |
| 7 | 7 | cnt ++, 종료 |
정답코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [10025] 게으른 백곰 (0) | 2023.01.13 |
|---|---|
| [14246] K보다 큰 구간 (0) | 2023.01.12 |
| [1504] 특정한 최단 경로 (0) | 2023.01.04 |
| [1238] 파티 (0) | 2023.01.04 |
| [2056] 작업 (0) | 2023.01.02 |