[2018] 수들의 합 5

https://www.acmicpc.net/problem/2018

2018번: 수들의 합 5

기초적인 투포인터 문제다.

 

풀이

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 ++, 종료

정답코드