푸키키키

문제 이해

삼각형 안에 숫자가 있고 만들 수 있는 부분 삼각형의 숫자 총합 중 최대값을 구하는 문제다. 숫자 범위가 정수이기 때문에 한 값이 튀게 되면 결과를 예상할 수 없어 모든 경우를 다 구해봐야한다.

평범한 dp로는 문제를 풀 수 없다. 메모이제이션 해야하는 양이

row : 400, col : 400 * 2 + 1, 부분삼각형 경우의수 : 400 으로 메모리 제한을 초과한다.

int memo[400][801][400] // 메모리 제한 초과 

모든 경우의 수를 다 구한다면 시간 복잡도는

r * c * 경우의수 * 경우의 수 뽑아 더하는 것 = 400 * 800 * 400 * 약 400 = 51,200,000,000

으로 시간제한 1초를 초과한다.

경우의 수를 뽑아 더하는 것은 처음 입력받을 때 누적 합을 구해 둔 다음 O(1)만에 한 row의 합을 구할 수 있도록 하면 시간제한안에 들어온다.

풀이

Process

void process() {
  for(int r=N-1;r>=0;--r) {
    for(int c=0;c<2*r+1;c+=2) {
      cal(r,c);
      if(c != 2 * r) {
        reverseCal(r,c+1);
      }
    }
  } 
 }

모든 점을 돌면서 한번씩 해봐야한다.

column은 짝수 번째일 때 size 2이상의 피라미드형 부분 삼각형을 만들 수 있다.

홀수 번째일때는 size 2 이상의 역삼각형을 만들 수 있다.

input 과 부분합

void input() {
  ans = -1001;
  memset(cSum, 0, sizeof(cSum));
  memset(table, 0, sizeof(table));
  for(int r=0;r<N;++r) {
    for(int c=0;c<2*r+1;++c) {
      cin >> table[r][c];
      ans = max(table[r][c], ans);
      if(c != 0) 
        cSum[r][c] += cSum[r][c-1] + table[r][c];
      else
        cSum[r][c] = table[r][c];
    }
  }
}

값 받으면서 부분합을 같이 계산해주었다.

피라미드형 부분 삼각형 계산

void cal(int r, int c) {
  int pSum = 0;
  for(int s=1;s<=N-r+1;++s) {
    if(c == 0) 
      pSum += cSum[r + s - 1][c + 2 * (s - 1)];
    else 
      pSum += cSum[r + s - 1][c + 2 * (s - 1)] - cSum[r + s - 1][c - 1];
    ans = max(pSum, ans);
  }
}

size는 지금 구해야 하는 row에서 더해야 하는 길이이다. size1 일 때는 r, c(시작점) 에서 부분 삼각형의 size 가 1일 때 값을 구하고 ans에 max값으로 최신화한다. 다음 size를 증가시키면서 한 row씩 증가시키며 해당하는 부분의 합을 더한다.

한 row에 해당하는 영역을 구하는 점화식이 위와 같이 나와 그대로 사용하면 된다.

역 피라미드형 부분 삼각형 계산

void reverseCal(int r, int c) {
 int pSum = 0;
  for(int s=1;s<=N;++s) {
    if(c >= 2 * s - 1 && 2 * r - c >= s * 2 - 1) {
      if(c - 2 * s + 1 >= 0) {
        pSum += cSum[r - s + 1][c] - cSum[r - s + 1][c - 2 * s + 1];
      } else {
        pSum += cSum[r - s + 1][c];
      }
    } else {
      break;
    }
    ans = max(pSum, ans);
  }
}

역 피라미드형은 row를 감소시키며 구해나간다. 점화식은 위와 같다.

종료조건을 따로 추가했다.

역 피라미드형이 가능한 size를 정하는데 위와 같은 방식으로 생각했다. 지금 size로 역 피라미드가 만들어지려면 선택한 c의 왼쪽, 오른쪽에 역피라미드의 가장 넓은 부분의 개수만큼 있어야 한다.

테스트 케이스

4 1 1 -1 1 1 -1 1 -1 1 1 -1 1 -1 1 -1 1
5 0 0 0 0 0 99 99 99 0 0 0 0 99 0 0 0 0 0 0 0 0 0 0 0 0
3 6 -24 0 12 -10 12 40 -4 6
5
         0
       0 0 0
     299 0 0 0 9
   -9 0 0 0 9 -9999 9
 -9 28 -9 0 9 9 9 9 9
5
         0
       0 0 0
     9 9 9 9 9
   0 -9 9 9 9 -9 0
 0 0 0 -9 9 -9 0 0 0
6
          0
        0 0 0
      0 1000 1000 1000 0
    0 9 9 -2 9 9 0
  0 0 0 9 9 9 0 0 0
0 0 0 0 0 9 -9999 0 0 0 0
6
          0
        0 0 0
      0 0 0 0 0
    0 9 9 9 9 9 0
  0 0 0 9 9 9 0 0 0
0 0 0 0 0 9 -9999 0 0 0 0
6
          0
        0 0 0
      0 1000 1000 1000 0
    0 9 9 -2 9 9 0
  0 0 0 9 9 9 0 0 0
0 0 0 0 0 9 -9999 0 0 0 0
0

// answer
1. 4
2. 396
3. 54
4. 336
5. 54
6. 3061
7. 81
8. 3061

코드

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int N;
int table[401][801];
int cSum[401][801];
int ans;
void input() {
  ans = -1001;
  memset(cSum, 0, sizeof(cSum));
  memset(table, 0, sizeof(table));
  for(int r=0;r<N;++r) {
    for(int c=0;c<2*r+1;++c) {
      cin >> table[r][c];
      ans = max(table[r][c], ans);
      if(c != 0) 
        cSum[r][c] += cSum[r][c-1] + table[r][c];
      else
        cSum[r][c] = table[r][c];
    }
  }
}

void cal(int r, int c) {
  int pSum = 0;
  for(int s=1;s<=N-r+1;++s) {
    if(c == 0) 
      pSum += cSum[r + s - 1][c + 2 * (s - 1)];
    else 
      pSum += cSum[r + s - 1][c + 2 * (s - 1)] - cSum[r + s - 1][c - 1];
    ans = max(pSum, ans);
  }
}

void reverseCal(int r, int c) {
 int pSum = 0;
  for(int s=1;s<=N;++s) {
    if(c >= 2 * s - 1 && 2 * r - c >= s * 2 - 1) {
      if(c - 2 * s + 1 >= 0) {
        pSum += cSum[r - s + 1][c] - cSum[r - s + 1][c - 2 * s + 1];
      } else {
        pSum += cSum[r - s + 1][c];
      }
    } else {
      break;
    }
    ans = max(pSum, ans);
  }
}

void process() {
  for(int r=N-1;r>=0;--r) {
    for(int c=0;c<2*r+1;c+=2) {
      cal(r,c);
      if(c != 2 * r) {
        reverseCal(r,c+1);
      }
    }
  } 
 }

void output() {
  static int cnt = 1;
  cout << cnt++ << ". " << ans << endl;
}

int main(void) {
  freopen("b4902.txt", "r", stdin);
  cin >> N;
  while(N != 0) {
    input();
    process();
    output();
    cin >> N;
  }
}