여러 테스트 케이스 · 알고리즘 노트

개념

테스트 케이스 수가 주어지는 입력

독립된 여러 입력을 한 번에 처리할 때 첫 값으로 테스트 케이스 수 $T$ 가 주어지는 형식이 자주 사용됩니다. 각 케이스의 입력·계산·출력을 $T$ 번 반복합니다.

합계, 방문 표시, 컨테이너처럼 케이스마다 달라지는 값은 각 케이스를 시작할 때 초기화합니다. 모든 케이스에서 같은 소수 표처럼 공통으로 사용하는 전처리 결과는 반복 전에 준비할 수 있습니다.

출력 형식

케이스 번호를 요구하는 문제는 지정된 접두사와 번호를 함께 출력합니다. 답만 요구하는 문제는 각 케이스의 답을 순서대로 출력합니다. 아래 예제는 케이스마다 합 하나를 출력합니다.

복잡도

각 케이스의 원소 수를 $N_i$ , 전체 원소 수를 $S=\sum_{i=1}^{T}N_i$ 라고 합니다.

연산	시간복잡도	공간복잡도
모든 케이스의 합 계산	$O(S)$	누적합용 추가 $O(1)$

예제

문제

각 테스트 케이스에 주어진 수들의 합을 구하여라.

입력

첫째 줄에 테스트 케이스 수 $T$ 가 주어진다. $1\le T\le100$ 이다.

각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에 원소 수 $n$ 이 주어진다. $1\le n\le100$ 이다. 둘째 줄에 $10\,000$ 보다 작은 양의 정수 $n$ 개가 공백을 사이에 두고 주어진다.

출력

각 케이스의 합을 한 줄씩 출력한다.

예제 코드

C++20

#include <iostream>

using namespace std;

int main() {
    int t, n, i, j, x, sum;

    cin >> t;
    for (i = 0; i < t; ++i) {
        cin >> n;
        // 케이스마다 합 초기화
        sum = 0;
        for (j = 0; j < n; ++j) {
            cin >> x;
            sum += x;
        }
        cout << sum << '\n';
    }
}

Java 17

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc;
        int t, n, i, j, x, sum;

        sc = new Scanner(System.in);
        t = sc.nextInt();
        for (i = 0; i < t; ++i) {
            n = sc.nextInt();
            // 케이스마다 합 초기화
            sum = 0;
            for (j = 0; j < n; ++j) {
                x = sc.nextInt();
                sum += x;
            }
            System.out.println(sum);
        }
    }
}

Python 3

t = int(input())

for _ in range(t):
    n = int(input())
    lst = list(map(int, input().split()))
    # 케이스마다 합 초기화
    total = 0
    for x in lst:
        total += x
    print(total)

3.3.3 Multiple Test Cases

개념

테스트 케이스 수가 주어지는 입력

출력 형식

복잡도

예제

문제

입력

출력

예제 입력

예제 출력

예제 코드