[백준/자바] 1806 부분합

1806 부분합 사진클릭시 문제로 이동

---

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다.

이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다.

둘째 줄에는 수열이 주어진다.

수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다.

만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

예제 입력 1

10 15
5 1 3 5 10 7 4 9 2 8

예제 출력 1

2

---

설명

시간 제한이 0.5초로 매우 짧기때문에 for문을 한번만 사용해야한다.

투 포인터와 부분합을 이용해 문제를 해결했다.

초기에는 left와 right 포인터 모두 0에서 시작한다.

 

1)

sum = 0

left
5	1	3	5	10	7	4	9	2	8
right

2)

right를 오른쪽으로 옮겨가며 전체 sum이 s보다 크거나 같을때까지 움직인다.

sum = 5

left
5	1	3	5	10	7	4	9	2	8
	right

3)

right를 오른쪽으로 옮겨가며 전체 sum이 s보다 크거나 같을때까지 움직인다.

sum = 6

left
5	1	3	5	10	7	4	9	2	8
		right

4)

right를 오른쪽으로 옮겨가며 전체 sum이 s보다 크거나 같을때까지 움직인다.

sum = 9

left
5	1	3	5	10	7	4	9	2	8
			right

5)

right를 오른쪽으로 옮겨가며 전체 sum이 s보다 크거나 같을때까지 움직인다.

sum = 14

left
5	1	3	5	10	7	4	9	2	8
				right

6)

right를 오른쪽으로 옮겨가며 전체 sum이 s보다 크거나 같을때까지 움직인다.

sum = 24

left
5	1	3	5	10	7	4	9	2	8
					right

7)

sum의 값이 s보다 크거나 같아졌으므로 right를 그대로 유지하고 left를 움직이면서 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구한다.

sum = 24

현재 = 5

최종 length = 5

left
5	1	3	5	10	7	4	9	2	8
					right

sum = 19

현재 = 4

최종 length = 5

	left
5	1	3	5	10	7	4	9	2	8
					right

sum = 18

현재 = 3

최종 length = 3

		left
5	1	3	5	10	7	4	9	2	8
					right

sum = 15

현재 = 2

최종 length = 2

			left
5	1	3	5	10	7	4	9	2	8
					right

sum = 10

				left
5	1	3	5	10	7	4	9	2	8
					right

8) 

right를 오른쪽으로 옮겼을때 sum의 값이 s보다 크거나 같아졌으므로 right를 그대로 유지하고 left를 움직이면서 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구한다.

sum = 17

현재 = 2

최종 length = 2

				left
5	1	3	5	10	7	4	9	2	8
						right

sum = 7

					left
5	1	3	5	10	7	4	9	2	8
						right

9)

right를 오른쪽으로 옮겨가며 전체 sum이 s보다 크거나 같을때까지 움직인다.

sum = 11

					left
5	1	3	5	10	7	4	9	2	8
							right

10)

right를 오른쪽으로 옮겼을때 sum의 값이 s보다 크거나 같아졌으므로 right를 그대로 유지하고 left를 움직이면서 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구한다.

sum = 20

현재 = 3

최종 length = 2

					left
5	1	3	5	10	7	4	9	2	8
								right

sum = 13

						left
5	1	3	5	10	7	4	9	2	8
								right

11)

right를 오른쪽으로 옮겼을때 sum의 값이 s보다 크거나 같아졌으므로 right를 그대로 유지하고 left를 움직이면서 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구한다.

sum = 15

현재 = 3

최종 length = 2

						left
5	1	3	5	10	7	4	9	2	8
									right

sum = 11

							left
5	1	3	5	10	7	4	9	2	8
									right

12)

최종 length = 2right를 오른쪽으로 옮겼을때 sum의 값이 s보다 크거나 같아졌으므로 right를 그대로 유지하고 left를 움직이면서 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구한다.

sum = 19

현재 = 3

최종 length = 2

							left
5	1	3	5	10	7	4	9	2	8
										right

sum = 10

								left
5	1	3	5	10	7	4	9	2	8
										right

최종적으로 가장 작은 길이였던 2가 닶이 된다.

코드