[백준] 4902 삼각형의 값 - Brute Force / Java

• 문제 링크

4902번: 삼각형의 값

 

• 풀이 과정

삼각형을 2차원 배열로 구현하여 단위 삼각형의 값을 입력받고, 각 행(삼각형의 층) 의 누적합을 pSum에 저장한다.

이 후 부분 삼각형이 정삼각형인 경우와 역삼각형인 경우의 수를 두 개의 2중 for 문을 통하여 구한다.

 

삼각형의 각 열(각 층의 단위 삼각형의 개수) 은 (2 * 행) - 1 의 길이를 가지므로,

모든 부분 정삼각형은 반복문의 범위(i = 1 ~ n, j = 1 ~ (2 * i) - 1) 에서 (i , j) 를 상단 꼭지점으로 가지고,

각각의 부분 정삼각형의 최대 크기는 n - i 이며,

모든 부분 역삼각형은 반복문의 범위(i = n ~ 1, j = 2 ~ 2 * i - 1) 에서 (i , j) 를 하단 꼭지점으로 가지고,

각각의 부분 역삼각형의 최대 크기는 j / 2 와 i - j / 2 중 작은 값이다.

 

이렇게 모든 부분 삼각형의 값을 구할 때마다 최대값으로 갱신하여, 각 테스트 케이스의 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

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

        int tc = 1;
        while (true) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());

            if (n == 0)
                break;

            int[][] tri = new int[n + 1][2 * n];
            int[][] pSum = new int[n + 1][2 * n];

            for (int i = 1; i <= n; i++) {
                for (int j = 1; j < 2 * i; j++) {
                    tri[i][j] = Integer.parseInt(st.nextToken());
                    pSum[i][j] = tri[i][j] + pSum[i][j - 1];
                }
            }

            int max = Integer.MIN_VALUE;

            for (int i = 1; i <= n; i++) {
                for (int j = 1; j < 2 * i; j += 2) {
                    int sum = 0;
                    for (int k = 0; k <= n - i; k++) {
                        sum += pSum[i + k][j + 2 * k] - pSum[i + k][j - 1];
                        max = Math.max(max, sum);
                    }
                }
            }

            for (int i = n; i >= 1; i--) {
                for (int j = 2; j < 2 * i; j += 2) {
                    int sum = 0;
                    for (int k = 0; k < Math.min(j / 2, i - j / 2); k++) {
                        sum += pSum[i - k][j] - pSum[i - k][j - 2 * k - 1];
                        max = Math.max(max, sum);
                    }
                }
            }

            bw.write(tc++ + ". " + max + "\n");
        }

        bw.flush();
    }

}