1. ๋ฌธ์ ์ค๋ช
2. ์ ๊ทผ ๋ฐฉ์
KEY WORD
: ๊ตฌ๊ฐํฉ
& ํฌ ํฌ์ธํฐ
๋ฐ์ดํฐ ํฌ๊ธฐ๊ฐ 10^5 ์ด๋ผ์ ์๊ฐ๋ณต์ก๋๊ฐ O(n^2) ์ด์์ด๋ฉด ์๋๋ค. ๋ฐ๋ผ์ ํ๋ฒ์ ์กฐํ์์ ๋ชจ๋ ๊ฒ์ ๋๋ด์ผ ํ๋ค. ๊ทธ๋ฌ๊ธฐ ์ํด์ ๋์ ํฉ์ ์ฌ์ฉํ์ฌ ๋ฌธ์ ๋ฅผ ํ์๋ค. ์งํ ๋ฐฉ์์ ๋ค์๊ณผ ๊ฐ๋ค.
- ์ ๋ ฅ์ ๋์ ํฉ ๋ฐฐ์ด(sum) ํํ๋ก ๋ง๋ ๋ค. (๋ค๋ง ์ง์ง ๋์ ํฉ์ ์์์ sum[1] ๋ถํฐ ์์ํ๊ณ , sum[0]=0 ์ผ๋ก ๋น์๋๋ค.)
- left, right ํฌ์ธํฐ๋ฅผ ๋ง๋ค๊ณ ๋ค์๊ณผ ๊ฐ์ด ์์ง์ธ๋ค.
(1) sum[right] - sum[left] < M ์ด๋ฉด right๋ฅผ ์์ง์ธ๋ค.
(2) sum[right] - sum[left] == M ์ด๋ฉด (right-left) ๊ธธ์ด ๊ธฐ๋ก ํ์, right๋ฅผ ์์ง์ธ๋ค.
(3) sum[right] - sum[left] > M ์ด๋ฉด (right - left) ๊ธธ์ด ๊ธฐ๋ก ํ์ left๋ฅผ ์์ง์ธ๋ค.
๐ค sum[right] - sum[left] > M ์ธ๋ฐ left๋ฅผ ++ ํ๋ ์ด์
๊ตฌ๊ฐํฉ์ด M ์ด์์ธ ๊ฒฝ์ฐ ์ค ๊ธธ์ด๊ฐ ์ ์ผ ์งง์ ๊ฒฝ์ฐ์ ์์ ๊ธธ์ด๋ฅผ ์ถ๋ ฅํด์ผ ํ๋ค. sum[right] - sum[left] > M ์ธ ๊ฐ์ ํ์ฌ ๋ง๋ฌ๋๋ฐ, ๋ right++ ์ ํด๋ฒ๋ฆฌ๋ฉด ์ด๋ฏธ ์ถฉ์กฑํ M ์ด์์ด๋ ์๊ฑด์์ ๊ธธ์ด๋ ๋ ๊ธธ์ด์ง๊ธฐ์ ์ธ๋ชจ ์๋ค.
๋ฐ๋ผ์ sum[right] - sum[left] > M ์ด๋ฉด ๊ธธ์ด ๊ธฐ๋ก ํ, left๋ฅผ ์ฌ๋ ค์, ์นธ ์๋ฅผ ์ค์ธ๋ค.
M์ผ๋ก ๋ง์ ๋จ์ด์ง์ง ์์ ์ ์๊ธฐ ๋๋ฌธ์ sum[right] - sum[left] > M์ธ ๊ฒฝ์ฐ๋ ์ธ์ด์ผ ํ๋ค.
3. ์ฝ๋ ๋ถ์
import java.io.*;
import java.util.*;
public class Main {
// ๊ตฌ๊ฐ ํฉ + ํฌ ํฌ์ธํฐ
// ์ ๊ตฌ์ญ์ ๋์ ํฉ์ ๊ตฌํ๋ค.
// sum[right] - sum[left] ์ target ๊ฐ์ ๋น๊ตํด์, right๋ left๋ฅผ ์ด๋ ์ํจ๋ค.
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st= new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
long [] sum = new long [N+1];
// 1. ๋์ ํฉ ๋ง๋ค๊ธฐ
st = new StringTokenizer(br.readLine());
sum[0] = 0;
sum[1] = Integer.parseInt(st.nextToken());
for (int i = 2; i <= N; i++) {
sum[i] = sum[i-1] + Integer.parseInt(st.nextToken());
}
// 2. ํฌํฌ์ธํฐ๋ก ๊ฐ ๊ตฌํ๊ธฐ
int left = 0, right = 0;
long cur_sum = 0;
long cur_len = Integer.MAX_VALUE;
while (right <= N){
cur_sum = sum[right] - sum[left];
if(cur_sum == M){
cur_len = Math.min(cur_len, right -left);
right++;
} else if (cur_sum < M) {
right++;
} else {
cur_len = Math.min(cur_len, right -left);
left++;
}
}
System.out.println(cur_len == Integer.MAX_VALUE? 0 : cur_len);
}
}