[자바] 백준 3724 - 표 (java)

 문제 : boj3724

---

 

필요 알고리즘 개념

• 큰 수 연산, 브루트포스
  
  • 문제에서 제시된 방식대로 모든 경우의수를 다 살펴보면 된다. 다만 엄청나게 큰 수 연산이 들어간..

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  주의점은 N과 M의 순서가 상당히 헷갈리게 들어오니 조심하자.

이 문제의 경우 모든 경우를 직접 해보면 된다. 즉, 각 열의 모든 수를 직접 다 곱해보고 비교하면 된다! 그러기 위해서는 대략 (2^31)^1000 이라는 천문학적으로 큰 수에 대한 연산이 필요하다. 다행히 자바의 경우 BigInteger가 무제한의 큰 수에 대한 곱셈 연산을 지원해준다. 

 

  각 테스트 케이스에 대한 로직은 아래와 같다.

int c = Integer.parseInt(st.nextToken());	// M에 해당한다. 내 경우엔 안헷갈리게 행과 열을 r과 c로 항상 표현한다.
int r = Integer.parseInt(st.nextToken());	// N에 해당한다.
BigInteger[] arr = new BigInteger[c];	// 열의 수만큼 해당 열의 모든 수의 곱을 계산할것이다.
for (int i = 0; i < c; i++) arr[i] = BigInteger.ONE;	// 처음엔 '1'로 초기화
while (r-->0) {	//각 행마다
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < c; i++) {
        arr[i] = arr[i].multiply(new BigInteger(st.nextToken()));	// 각 열에 곱해준다.
    }
}
BigInteger max = arr[0];	// default는 첫번째 수
int maxIdx = 0;
for (int i = 1; i < c; i++) {	// 인덱스 기준 1번이므로, 2번째 수부터 보는것이다.
    if (max.compareTo(arr[i])<=0) {	// 현재 보고있는게 크거나 같다면(동일한 값의 열이 여러개라면 가장 큰 열을 출력해야 하므로 같아도 변경한다)
        max = arr[i];	// 가장 큰 수를 변경
        maxIdx = i;	// 해당 가장 큰 수의 인덱스를 기록
    }
}
sb.append(maxIdx+1).append('\n');	// 위에는 인덱스를 기준으로 했으므로 'n번째'로 출력하기 위해 +1을 해준다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (tc-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int c = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            BigInteger[] arr = new BigInteger[c];
            for (int i = 0; i < c; i++) arr[i] = BigInteger.ONE;
            while (r-->0) {
                st = new StringTokenizer(br.readLine());
                for (int i = 0; i < c; i++) {
                    arr[i] = arr[i].multiply(new BigInteger(st.nextToken()));
                }
            }
            BigInteger max = arr[0];
            int maxIdx = 0;
            for (int i = 1; i < c; i++) {
                if (max.compareTo(arr[i])<=0) {
                    max = arr[i];
                    maxIdx = i;
                }
            }
            sb.append(maxIdx+1).append('\n');
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}