백준 2143번
https://www.acmicpc.net/problem/2143

문제

---

생각하기

---

• 누적 합, 자료구조 문제이다.

동작

A의 부 배열의 합을 모두 계산하고 이 계산 내용을 HashMap()에 저장한다.

getOrDefault() 메소드를 통해 같은 부 배열의 합의 개수까지 파악한다.

        HashMap<Long, Integer> nPrefixSum = new HashMap<>();
        for (int i = 0; i < N; i++) {
            long sum = 0;
            for (int j = i; j < N; j++) {
                sum += nArr[j];
                nPrefixSum.put(sum, nPrefixSum.getOrDefault(sum, 0) + 1);
            }
        }

이후 다음 B의 부 배열에서 계산하면서 T - B 부배열 값을 했을 때 A의 부배열과 같은 값이 있으면

이 값은 만들 수 있는 경우이고 경우의 수는 A 부배열 개수 합을 더하면 된다.

        long count = 0;
        for (int i = 0; i < M; i++) {
            long sum = 0;
            for (int j = i; j < M; j++) {
                sum += mArr[j];
                if (nPrefixSum.containsKey(T - sum)) {
                    count += nPrefixSum.get(T - sum);
                }
            }
        }

결과

코드

---

import java.io.*;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int T, N, M;
    private static int[] nArr, mArr;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        HashMap<Long, Integer> nPrefixSum = new HashMap<>();
        for (int i = 0; i < N; i++) {
            long sum = 0;
            for (int j = i; j < N; j++) {
                sum += nArr[j];
                nPrefixSum.put(sum, nPrefixSum.getOrDefault(sum, 0) + 1);
            }
        }

        long count = 0;
        for (int i = 0; i < M; i++) {
            long sum = 0;
            for (int j = i; j < M; j++) {
                sum += mArr[j];
                if (nPrefixSum.containsKey(T - sum)) {
                    count += nPrefixSum.get(T - sum);
                }
            }
        }

        sb.append(count);
        return sb.toString();
    } // End of solve()

    private static void input() throws IOException {
        T = Integer.parseInt(br.readLine());

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

        M = Integer.parseInt(br.readLine());
        mArr = new int[M];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= M; i++) {
            mArr[i - 1] = Integer.parseInt(st.nextToken());
        }
    } // End of input()
} // End of Main class

Kotlin

import java.io.BufferedReader
import java.io.File
import java.util.StringTokenizer

// input
private var br = System.`in`.bufferedReader()

// variables
private var T = 0
private var N = 0
private var M = 0
private lateinit var nArr: IntArray
private lateinit var mArr: IntArray
private lateinit var map: HashMap<Long, Int>

fun main() {
    val bw = System.out.bufferedWriter()

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    map = HashMap()
    for (i in 0 until N) {
        var sum = 0L
        for (j in i until N) {
            sum += nArr[j]
            map.put(sum, map.getOrDefault(sum, 0) + 1)
        }
    }

    var ans = 0L
    for (i in 0 until M) {
        var sum = 0L
        for (j in i until M) {
            sum += mArr[j]
            val temp = T - sum
            if (map.contains(temp)) {
                ans += map[temp]!!
            }
        }
    }

    sb.append(ans)
    return sb.toString()
} // End of solve()

private fun input() {
    T = br.readLine().toInt()
    N = br.readLine().toInt()

    var st = StringTokenizer(br.readLine())
    nArr = IntArray(N) {
        st.nextToken().toInt()
    }

    M = br.readLine().toInt()
    st = StringTokenizer(br.readLine())
    mArr = IntArray(M) {
        st.nextToken().toInt()
    }
} // End of input()