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

 

문제

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

 

 

입력값	- n: 수열의 갯수 - m: 수열의 i번째 수부터 j번째 수까지의 구하고자 하는 합 - n개의 수열
출력값	수열의 i번째 수부터 j번째 수까지의 합이 m이 되는 경우의 수

 

 

풀이 방법

 

이 문제는 이중 반복문을 사용하여 해결하였다.

각 수열의 요소를 시작으로 하여 합이 m이 되면 경우의 수를 1씩 더해주었다.

그리고 m을 초과하게 되면 반복문을 종료하고 다음 수열  i 요소에서 j 요소까지 합 m이 되면 경우의 수를 업데이트 하였다.

 

 

누적합과 그리드 알고리즘에 대한 기초 문제라고 생각한다.

특히, 구간의 합을 구하는 개념이 사용되는 문제를 풀 때 도움이 될 것 같다.

 

 

 

작성 답안

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {
    public static void main(String[] args) throws IOException {
        // 1. 입력값
        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()); // 총합

        st = new StringTokenizer(br.readLine());
        int[] number_array = new int[n];
        for (int i = 0; i < n; i++) {
            number_array[i] = Integer.parseInt(st.nextToken());
        }


        // 2. 숫자 더하기
        int cnt = 0;
        for (int i = 0; i < n; i++){
            int tmp_sum = 0;

            for (int j = i; j < n; j++) {
                tmp_sum += number_array[j];

                if (tmp_sum == m){
                    cnt += 1;
                }
                else if (tmp_sum > m) {
                    break;
                }
            }
        }
        System.out.println(cnt);

    }
}

 

 

 

---

 

코테.. 가보자고..!