백준 4902번 https://www.acmicpc.net/problem/4902
문제
오른쪽 삼각형은 9개의 단위 삼각형이 총 3줄(N=3)로 이루어져 있다. 단위 삼각형은 N=1인 삼각형이다.
이때, 그림에서 서로 다른 부분 삼각형은 총 13개가 있다. (N=1인 삼각형이 9개, N=2인 삼각형이 3개, N=3인 삼각형이 1개)
N = 1인 경우 부분 삼각형은 1개, 2인 경우에는 5개, 3인 경우는 13개, 4인 경우는 27개가 있다.
이때, 단위 삼각형의 값을 삼각형 내부에 쓰여 있는 숫자의 값이라고 하자. 삼각형의 값은 삼각형 안에 있는 단위 삼각형의 값의 합이다.
오른쪽 그림은 가장 큰 값을 갖는 부분 삼각형이다.
삼각형이 주어졌을 때, 가장 큰 값을 갖는 부분 삼각형을 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있고, 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 숫자는 줄의 수를 나타내고, 다음 숫자는 단위 삼각형에 적혀있는 값이 위에서 아래, 왼쪽에서 오른쪽 순서대로 주어진다. 마지막 줄에는 0이 주어진다.
줄의 개수는 400을 넘지 않으며, 단위 삼각형에 적혀있는 값의 절댓값은 1000을 넘지 않는다.
출력
각 테스트 케이스에 대해서, 테스트 케이스의 번호와 가장 큰 부분 삼각형의 값을 출력한다.
예제
입력
1
2
3
3 6 -24 0 12 -10 12 40 -4 6
4 1 1 -1 1 1 -1 1 -1 1 1 -1 1 -1 1 -1 1
0
출력
1
2
1. 54
2. 4
삼각형의 값을 가져야 하기 때문에 접근하기 편하게 하기 위해서 값을 2차원 배열의 형식으로 입력받았다.
그러면 다음과 같은 형태로 접근이 가능하다.
모든 크기의 삼각형을 검사하는 방법을 생각해 내는 것이 이 문제의 포인트같다. 나는 크기가 작든지, 크든지 행의 크기가 1인 삼각형이 존재하기 때문에 이를 기준으로 삼으면 될것이라고 생각했다.
위의 그림을 보면 기준으로 예시를 들자면,
- 기준이 되는 n=1 크기의 삼각형을 정한다. 그림에서는 기준이 (0, 0)이 된다.
- 다음 행이 존재하면, 기준을 포함하는 삼각형을 계산한다.
- 다음 행이 존재하지 않을 때까지 [2번]을 반복한다.
위의 그림과 같이 기준이 제일 위에 존재하는 경우에는 삼각형의 (a, b)라고 했을 때, b가 짝수인 경우이다.
반대로, b가 홀수인 경우에는 n=1 크기의 삼각형이 제일 밑에 있는 삼각형(역삼각형)의 형태가 된다.
가장 밑에 있는 삼각형의 값 경우에는 b가 짝수인 모든 삼각형이 접근해야한다. 즉, 접근할때마다 합을 구하게 되면 n이 커질 수록 동일한 연산을 반복하게 된다. 이를 방지하기 위해서 같은 행에 대한 누적합(prefix sum)값을 구해놓았다.
1
int[][] prefixSum; // 누적합
코드 (Java)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Bj4902 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
public static int n, answer; // n의 최댓값은????????
public static int[][] nums, prefixSum;
public static void main(String[] args) throws IOException {
int number = 1, a, sum;
while (input()) {
answer = -1000;
for (int i = 0; i < n; i++) {
for (int j = 0; j < 2 * i + 1; j++) {
a = i;
if (j % 2 == 0) { // 짝수 - 정삼각형
sum = 0;
while(a < n) {
sum += getLineSum(a, j, j + (a-i) * 2);
answer = Math.max(sum, answer);
a++;
}
} else { // 홀수 - 역삼각형
sum = nums[a--][j];
while (a >= 0 && j - (i-a) * 2 >= 0 && j < 2*a+1) {
sum += getLineSum(a,j - (i-a) * 2, j);
answer = Math.max(sum, answer);
a--;
}
}
}
}
System.out.println(number + ". " + answer);
number++;
}
}
// nums[a][bStart] ~ nums[a][bEnd]까지의 합을 반환 (가로줄의 합)
public static int getLineSum(int a, int bStart, int bEnd) {
if (bStart == 0) return prefixSum[a][bEnd];
return prefixSum[a][bEnd] - prefixSum[a][bStart-1];
}
// 입력값 받기
public static boolean input() throws IOException {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken()); // 1 ≤ n ≤ 400
if (n == 0) return false;
nums = new int[n][2*n-1];
prefixSum = new int[n][2*n-1];
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = 0; j < 2 * i + 1; j++) {
nums[i][j] = Integer.parseInt(st.nextToken());
sum += nums[i][j];
prefixSum[i][j] = sum;
}
}
return true;
}
}
메모리는 56384 KB, 시간은 728ms가 나왔다.
문제에 n의 범위가 주어져 있지 않아서 answer을 int형으로 해봤는데 통과가 됐다.