๐ง ๋ฌธ์
https://www.acmicpc.net/problem/1806
<๋ฌธ์ >
10,000 ์ดํ์ ์์ฐ์๋ก ์ด๋ฃจ์ด์ง ๊ธธ์ด N์ง๋ฆฌ ์์ด์ด ์ฃผ์ด์ง๋ค. ์ด ์์ด์์ ์ฐ์๋ ์๋ค์ ๋ถ๋ถํฉ ์ค์ ๊ทธ ํฉ์ด S ์ด์์ด ๋๋ ๊ฒ ์ค, ๊ฐ์ฅ ์งง์ ๊ฒ์ ๊ธธ์ด๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
<์ ๋ ฅ>
์ฒซ์งธ ์ค์ N (10 ≤ N < 100,000)๊ณผ S (0 < S ≤ 100,000,000)๊ฐ ์ฃผ์ด์ง๋ค. ๋์งธ ์ค์๋ ์์ด์ด ์ฃผ์ด์ง๋ค. ์์ด์ ๊ฐ ์์๋ ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถ๋์ด์ ธ ์์ผ๋ฉฐ, 10,000์ดํ์ ์์ฐ์์ด๋ค.
<์ถ๋ ฅ>
์ฒซ์งธ ์ค์ ๊ตฌํ๊ณ ์ ํ๋ ์ต์์ ๊ธธ์ด๋ฅผ ์ถ๋ ฅํ๋ค. ๋ง์ผ ๊ทธ๋ฌํ ํฉ์ ๋ง๋๋ ๊ฒ์ด ๋ถ๊ฐ๋ฅํ๋ค๋ฉด 0์ ์ถ๋ ฅํ๋ฉด ๋๋ค.
<์์ >
10 15
5 1 3 5 10 7 4 9 2 8
๐ธ์์ ํ์? →๐จ์๊ฐ์ด๊ณผ
์ฃผ์ด์ง ์์ด์์ ์ฐ์๋ ๋ถ๋ถ ์์ด์ ํฉ์ด S ์ด์์ด ๋๋ ๊ฐ์ฅ ์งง์ ๊ธธ์ด๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์ด๋ค.
์ด๊ฑธ ์ฒ์ ์ ํ๋ฉด for๋ฌธ์ ์ค์ฒฉํด์ ์ฌ์ฉํ๋ ๋ฐฉ์์ด ์ ์ผ ๋จผ์ ๋ ์ค๋ฅผ ๊ฒ์ด๋ค.
int minLength = Integer.MAX_VALUE;
for (int i = 0; i < N; i++) {
int sum = 0;
for (int j = i; j < N; j++) {
sum += arr[j];
if (sum >= S) {
minLength = Math.min(minLength, j - i + 1);
break;
}
}
}
ํ์ง๋ง ์ด๋ ๊ฒ ์คํ์ํค๋ฉด ์๊ฐ์ด๊ณผ๋ก ์ธํด ๋ฌธ์ ๋ฅผ ํ๋ฆฌ๊ฒ ๋ ๊ฒ์ด๋ค.
๋ฌธ์ ์ ์กฐ๊ฑด๋ฌธ์ ๋ค์ ์ดํด๋ณด๋ฉด for๋ฌธ์ ๋๋ ํ์๋ ๋ค์๊ณผ ๊ฐ์ ๊ฒ์ด๋ค.
- ๋ฐ๊นฅ ๋ฐ๋ณต๋ฌธ: ์ต๋ 100,000๋ฒ
- ์์ชฝ ๋ฐ๋ณต๋ฌธ: ํ๊ท 50,000๋ฒ → ์ต์ ์ ๊ฒฝ์ฐ์ ๊ฑฐ์ N๋ฒ์ฉ ๋ฐ๋ณต
๊ทธ๋ฌ๋ฉด ์๊ฐ๋ณต์ก๋๋ ์ต์ ์ ๊ฒฝ์ฐ 100,000 × 100,000 = 10,000,000,000 (100์ต) ์ด ๋๋ฏ๋ก, ์๊ฐ์ด๊ณผ๊ฐ ๋๋ ๊ฒ์ด๋ค.
๋ฐ๋ผ์ ์์ ๊ฐ์ ๋ฌธ์ ๋ ํฌ ํฌ์ธํฐ(์ฌ๋ผ์ด๋ฉ ์๋์ฐ) ๋ฐฉ์์ ์ฌ์ฉํด์ผํ๋ค.
๐ธํฌ ํฌ์ธํฐ ํ์ด ๋ฐฉ์
ํฌ ํฌ์ธํฐ: 1์ฐจ์ ๋ฐฐ์ด์์ ๊ฐ์ ๋ค๋ฅธ ์์๋ฅผ ๊ฐ๋ฆฌํค๋ 2๊ฐ์ ํฌ์ธํฐ๋ฅผ ํ์ฉํ์ฌ ๋ชฉํ๊ฐ์ ๊ตฌํด๋๊ฐ๋ ๋ฐฉ์์ด๋ค.
์ด ๋ฐฉ์์ ํ๋์ ๋ฐ๋ณต๋ฌธ ๋ด์์ ์กฐ๊ฑด์ ๋ฐ๋ผ ๋ ํฌ์ธํฐ๋ฅผ ๊ฐ๊ฐ ์์ง์ด๋ฉฐ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ๋๋ฌธ์, ์ผ๋ฐ์ ์ผ๋ก ์๊ฐ ๋ณต์ก๋๋ O(N)์ผ๋ก ๋งค์ฐ ํจ์จ์ ์ด๋ค.
ํฌํฌ์ธํฐ๊ฐ ํจ๊ณผ์ ์ธ ๊ฒฝ์ฐ๋ ๋ค์๊ณผ ๊ฐ๋ค.
- ์ฐ์๋ ๊ตฌ๊ฐ์ ์์๋ค์ ์ฒ๋ฆฌํด์ผ ํ ๋
- ์ ๋ ฌ๋ ๋ฐฐ์ด์์ ์กฐ๊ฑด์ ๋ง์กฑํ๋ ์์ด๋ ๋ถ๋ถํฉ ๋ฑ์ ์ฐพ์ ๋
ํฌํฌ์ธํฐ์ ๋ฐฉ์์ผ๋ก ์์ ๋ฌธ์ ๋ฅผ ํ๊ณ ์ ํ๋ค.
1๏ธโฃ ์กฐ๊ฑด๋ฌธ ์ค์ ํ๊ธฐ
์์ ๊ฐ์ ๋ฐฐ์ด์ด ์๋ค๊ณ ๊ฐ์ ํ์ ๋, ๋ ๊ฐ์ ํฌ์ธํฐ๋ฅผ ํตํด์ S=15 ์ด์์ธ ๊ฒฝ์ฐ๋ฅผ ์ฐพ๊ณ ์ ํ๋ค.
left์ right์ index๋ฅผ ์ค์ ํ๋ ๋ฐฉ์์๋ ํฌ๊ฒ ๋ ๊ฐ์ง๊ฐ ์๋ค.
- left, right ๋ ๋ค index 0๋ถํฐ ์์ํ๋ฉด์ ํ์
- left๋ index 0, right๋ index end๋ก ์ค์ ํ๋ฉด์ ํ์ ~> ์ด๋ถํ์
๋ณดํต ์ฐ์์ฑ์ ๋ฐ์ ธ์ผํ๋ ๊ฒฝ์ฐ์๋ left์ right์ index๋ฅผ 0์ผ๋ก ๋๋ฉด์ ํ์์ ์๋ํ๋ค.
์์ ๊ฐ์ ๋ฌธ์ ์์๋ ํฌ๊ฒ ๋ฐ๋ผ๋ณด๋ฉด a~b์ ๊ตฌ๊ฐ ์ค ์ต์ ๊ตฌ๊ฐ์ ์ฐพ๋ ๊ฒ์ด๋ฏ๋ก ์ ์์ ํด๋นํ๋ ๋ฌธ์ ์ด๋ค.
๋ฐ๋ผ์ left์ right์ index๋ฅผ 0์ผ๋ก ์ค์ ํด์ผํ๋ค.
๊ทธ๋ ๋ค๋ฉด ๋ค์์ผ๋ก ๊ณ ๋ คํด์ผํ ๋ถ๋ถ์ ์ด๋ค ๊ฒฝ์ฐ์ left์ right์ index๋ฅผ ์กฐ์ ํ ๊ฒ์ธ๊ฐ์ ๋ํ ๋ฌธ์ ์ด๋ค.
๋ณดํต ๋ ๋ค index๋ฅผ 0๋ถํฐ ์์ํ๋ ๊ฒฝ์ฐ์๋ ๋ค์๊ณผ ๊ฐ์ด ์กฐ๊ฑด์ ์ค์ ํ๋ค.
1. S > sum : right ++
2. S < sum : left ++
3. S = sum : ์กฐ๊ฑด ์ฒ๋ฆฌ -> left ++
ํ์ง๋ง ์์ ๋ฌธ์ ์ธ ๊ฒฝ์ฐ์๋ S=15 ์ด์์ธ ๊ตฌ๊ฐ์ ๊ตฌํ๋ ๊ฒ ๋ชฉ์ ์ด๋ฏ๋ก ๋ค์๊ณผ ๊ฐ์ด ์กฐ๊ฑด์ ๋ณํ์ํฌ ์ ์๋ค.
1. S > sum : right ++
2. S <= sum : ์กฐ๊ฑด ์ฒ๋ฆฌ -> left ++
์์ ๊ฐ์ด ์กฐ๊ฑด์ ์ค์ ํ์์ผ๋ฏ๋ก ์ด์ ์ ํํ ๋์์๋ฆฌ๋ฅผ ๊ทธ๋ฆผ์ ํตํด ์ดํดํ๊ณ ์ ํ๋ค.
2๏ธโฃ ํฌํฌ์ธํฐ ๋์ ์๋ฆฌ
๊ทธ๋ฆผ์ ํตํด left์ right์ ํฌ์ธํฐ ๋ณํ๋ฅผ ์ดํด๋ณด๊ณ ์ ํ๋ค.
์์ ๊ฐ์ด left์ right์ ํฌ์ธํฐ๊ฐ ์ค์ ๋์์ ๋ ์ต์์ ๊ตฌ๊ฐ์ด ๋์ค๊ฒ ๋๋ค. ์ดํ์ ๊ณผ์ ์ ์๋ตํ๊ฒ ๋ค.
(๊ทธ ์ดํ๋ก๋ ์์ ๊ฐ์ ๊ณผ์ ์ด ๋ฐ๋ณต๋๋ฉฐ ์ต์ ๊ตฌ๊ฐ์ ๊ณ์ํด์ ์ฐพ์ ๊ฒ์ด๋ค..)
3๏ธโฃ ์กฐ๊ฑด๋ฌธ ์ฝ๋ ๊ตฌํ
while (true) {
if (sum >= S) {
minLength = Math.min(minLength, right - left); // ์ต์ ๊ตฌ๊ฐ ๊ฐฑ์
sum -= arr[left++];
} else if (right == N) {
break;
} else { // sum < S
sum += arr[right++];
}
}
์์ ๋์๊ณผ์ ์ ์ฝ๋๋ก ๋ํ๋ด๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.
- sum >= s : ์ต์๊ตฌ๊ฐ์ ๊ณ์ํด์ ๊ฐฑ์ ํ๋ค, left ํฌ์ธํฐ๋ฅผ ์์ง์ด๋ฏ๋ก ์ ์ ์์๋ ๊ฐ์ ๋บ๋ค
- right == N: ํ์ถ ์กฐ๊ฑด
- else : sum < S์ ์ํฉ์ผ๋ก, sum์ ์ฆ๊ฐ๋ right index์ ๊ฐ์ ๋ํด์ค๋ค.
๐ธ์ ์ฒด ์ฝ๋
// 1806 ๋ถ๋ถํฉ
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int S = Integer.parseInt(st.nextToken());
int[] arr = new int[N];
StringTokenizer st2 = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i ++){
arr[i] = Integer.parseInt(st2.nextToken());
}
int left = 0;
int right = 0;
int sum = 0;
int minLength = Integer.MAX_VALUE;
while (true) {
if (sum >= S) {
minLength = Math.min(minLength, right - left); // ์ต์ ๊ตฌ๊ฐ ๊ฐฑ์
sum -= arr[left++];
} else if (right == N) {
break;
} else { // sum < S
sum += arr[right++];
}
}
if (minLength == Integer.MAX_VALUE){
System.out.println(0);
}else{
System.out.println(minLength);
}
}
}