BOJ_2003 : 수들의 합 2

👉 문제링크

2003번: 수들의 합 2

---

---

🔸 문제 분석 🔸

• n개의 숫자의 합으로 m을 만들 수 있는 경우의 수를 출력한다.
• m은 3억이므로 int형으로 충분하다.
• n개의 수의 합이 m이 되는지 매번 더해서 확인하면 시간초과가 날 것이다.
  • 따라서 미리 누적 합 리스트 sum를 만들어 둔다.
  • 인덱스 i부터 인덱스 j 까지의 합은 sum[j] - sum[i] 로 구할 수 있다.
  • sum[0]은 0이다.
  • sum[j] - sum[i] > m이면, 계속 커지는 방향인 다음 j를 확인하는 걸 멈추고 다음 i를 확인한다.

🔸 코드 🔸

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 {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        final int n = Integer.parseInt(st.nextToken());
        final int m = Integer.parseInt(st.nextToken());
        int sum[] = new int[n+1];
        sum[0] = 0;

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

        int answer = 0;
        for (int i = 0; i <= n; i++){
            for (int j = i + 1; j <= n; j++){
                if (sum[j] - sum[i] == m) {
                    answer++;
                    break;
                }
            }
        }
        System.out.println(answer);
    }
}

🔸 코드 해석 🔸

• n개의 수를 sum[1]부터 sum[n]에 저장한다.
  • sum[0] 은 0이다.
  • i>0일때, sum[i] = sum[i-1] + 입력수로 누적해가며 저장한다.
• i부터 j의 합은 sum[j] - sum[i]로 구할 수 있다.
  • 값이 m이면 answer++
  • j를 더 키워봤자 m을 초과하므로 break해준다.

 

---

🔸 end 🔸

• 부분 합 문제로 생각했는데 태그는 투 포인터로 달려있었다.
• 다시 개념을 확인해보니 부분 합 개념안에 투 포인터가 녹아있는 것 같다.
• 코드에서 sum[i] - sum[j] == m 인 경우에만 조기 종료되는데, sum[i] - sum[j] > m 경우에도 조기 종료를 해줘야 더 빠른 코드가 된다고 생각해서 수정후 채점해 봤지만 시간은 동일했다. 테스트 케이스가 차이가 안나는 케이스 인 것 같다.