[백준 / 실버4] 2003 수들의 합 2 (Java)

Ilhwanee·2022년 12월 12일
0

코딩테스트

목록 보기
143/155

문제 보기



사용한 것

  • 배열의 i 번째 인덱스 ~ j 번째 인덱스 까지의 합을 효율적으로 구하기 위한 누적합
  • O(N)으로 배열의 가능한 구간을 탐색하기 위한 투포인터


풀이 방법

  • 입력 값으로 누적합을 sum에 저장한다.
  • 투포인터와 sum을 사용하여
    • 현재 구간의 합이 m과 같으면 answer 증가, r 증가
    • 현재 구간의 합이 m보다 크면 l 증가
    • 현재 구간의 합이 m보다 작거나 lr이 같으면 r 증가


코드

public class Main {

    public static void main(String[] args) throws IOException {
        // 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] sum = new int[n + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            int num = Integer.parseInt(st.nextToken());
            sum[i] = sum[i - 1] + num;
        }

        // 투포인터
        int answer = 0;
        int l = 0;
        int r = 1;
        while (l < r && r <= n) {
            int diff = sum[r] - sum[l];
            if (diff == m) {
                answer++;
            }
            if (diff > m) {
                l++;
            }
            if (diff <= m || l == r) {
                r++;
            }
        }

        System.out.println(answer);
    }
}


profile
블로그 이전 -> https://pppp0722.github.io

0개의 댓글