BOJ 3724 - 표

문제

BOJ 3724 - 표

M개의 열과 N개의 행으로 이루어진 표가 주어질 때, 각 열의 모든 행 값을 곱한 결과가 가장 큰 열을 찾는 문제이다. 값이 같은 열이 여러 개면 인덱스가 가장 큰 열을 출력한다. Python의 임의 정밀도 정수 연산을 활용하면 큰 수 처리가 자연스럽다.

입력

첫 줄에 테스트 케이스 수 T가 주어진다. 각 케이스 첫 줄에 열 수 M과 행 수 N이 주어진다. 이후 N줄에 걸쳐 M개의 정수가 주어진다.

출력

각 테스트 케이스마다 곱이 가장 큰 열 번호(1-indexed)를 출력한다. 동점 시 인덱스가 큰 열을 출력한다.

예제

풀이

각 열의 행 값을 순서대로 누적 곱하여 열별 곱을 구한 뒤, 최댓값을 가진 열을 찾는다. 동점 처리를 위해 같은 값이면 더 큰 인덱스로 갱신한다.

1. 모든 입력을 한 번에 읽어 이터레이터로 처리하여 I/O 속도를 향상시킨다.
2. 테스트 케이스마다 크기 M의 products 배열을 1로 초기화한다.
3. N개의 행을 읽으며 각 열 j에 대해 products[j] *= 값으로 누적 곱을 계산한다.
4. products를 순회하며 현재 최대보다 크거나 같고 인덱스가 더 크면 갱신한다.
5. 결과를 수집 후 한 번에 출력하여 성능을 최적화한다.

핵심 아이디어: Python의 임의 정밀도 정수 덕분에 큰 수 오버플로 걱정 없이 열별 곱을 직접 계산할 수 있다.

코드

import sys
 
 
def solve() -> None:
    it = iter(sys.stdin.read().strip().split())
    t = int(next(it))
    out_lines = []
    for _ in range(t):
        m = int(next(it))
        n = int(next(it))
 
        products = [1] * m
        for _ in range(n):
            for j in range(m):
                products[j] *= int(next(it))
 
        best_idx, best_val = 1, products[0]
        for j in range(1, m):
            val = products[j]
            if val > best_val or (val == best_val and j + 1 > best_idx):
                best_idx, best_val = j + 1, val
 
        out_lines.append(str(best_idx))
 
    sys.stdout.write("\n".join(out_lines))
 
 
if __name__ == "__main__":
    solve()

복잡도

• 시간: O(T * M * N) — T개 케이스, M열 N행 전체 순회
• 공간: O(M) — 열별 누적 곱 배열