푸키키키

문제 이해

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

평범한 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;
  }
}

문제 링크

• https://www.acmicpc.net/problem/2933

풀이

eraseBlock();
rootedClusterCheck();
flyClusterDown();

eraseBlock();

왼쪽, 오른쪽에서 막대기를 던질 때 해당하는 block을 제거하는 로직.

rootedClusterCheck();

rooted → 땅에 박혀있는 이라는 의미로 변수명 지었다. 땅(row == 0) 까지 연결되어 있는 클러스터는 땅으로 떨어지지 않기 때문에 먼저 땅과 연결되어 있는 클러스터들을 체크해줬다.

체크한 방법은 row == 0에 있는 것 중에서 x가 있으면 그걸 시작점으로 dfs를 돌면서 연결되어 있는 것들을 체크했다.

flyClusterDown();

앞에서 땅과 연결되어 있는 클러스터들은 체크가 됐다. 그렇다면 입력 테이블에서 'x'이면서 땅과 연결된 클러스터로 체크되지 않은 것은 모두 공중에 있는 클러스터일 것이다. 문제조건에 두 개 이상의 클러스터는 공중에 있지 않다고 했으므로 해당하는 x를 만나면 거기서 dfs를 통해 공중에 있는 클러스터들을 체크해줬다.

그리고 이 클러스터를 땅이나 만나는 미네랄에 연결시켜줘야 한다. 이 클러스터는 전체적으로 똑같은 col만큼 아래로 하강하는데 이 값을 효율적으로 구하기 위해 dfs돌면서 각 column의 가장 작은 row값을 따로 저장해 뒀다.

int findDownLength() {
  int minLength = 9999999;
  for(int j=0;j<c;++j) {
    if(columnList[j] == 999999) continue;
    for(int i=0;i<r;++i) {
      if(table[i][j] == 'x') {
        if(i == columnList[j]) {
          minLength = min(minLength, i);
          break;
        } else {
          minLength = min(columnList[j] - i - 1, minLength);
        }
      }
    }
  }
  return minLength;
}

이 값들은 위와 같은 코드에 사용되는데 땅부터 row를 증가시키면서 찾다가 테이블에 'x'를 만났다면 두 가지 경우중 하나이다.

첫 번째는 공중에 떠있는 자기자신을 만났을 때,

두 번째는 다른 땅과 연결된 클러스터를 만났을 때이다.

전자는 자기를 만났기 때문에 자기 위쪽은 탐색할 필요 없다. 그래서 클러스터를 몇칸 땅으로 이동시킬지에 대한 변수인 minLength를 자기 row값으로 min(minLength, i)로 최신화 시켜주었다.

후자는 지금 만난 x보다 더 위에도 x가 존재할 수 있고, 그 때에는 minLength가 더 작아지기 때문에 추가적인 탐색이 필요해 break를 걸지 않았다.

이렇게 몇칸 아래로 내릴지 구한다음 공중에 떠있는 클러스터들은 모두 체크가 되어 있기 때문에 그 칸만큼 내려준다.

이 3가지 과정을 N번 진행하면 문제가 풀린다.

코드

#include <iostream>
#include <vector>

using namespace std;

char table[101][101];

int r, c;
bool isrootedCluster[101][101];
void rootedClusterClear() {
  for(int i=0;i<r;++i) {
    for(int j=0;j<c;++j) {
      isrootedCluster[i][j] = false;
    }
  }
}

vector<int> stickThrowRow;

void input() {
  cin >> r >> c;
  for(int i=0;i<r;++i) {
    for(int j=0;j<c;++j) {
      cin >> table[r-i-1][j];
    }
  }
  int n;
  cin >> n;
  int temp;
  for(int i=0;i<n;++i) {
    cin >> temp;
    stickThrowRow.push_back(temp); 
  }
}

bool blockErase(int row, int col) {
  if(table[row][col] == 'x') {
    table[row][col] = '.';
    return true;
  }
  return false;
}

void eraseBlock(int throwIdx, bool isRightToLeft) {
  if(isRightToLeft) {
    for(int i=0;i<c;++i) {
      if(blockErase(throwIdx, i)) return;
    }
  } else {
    for(int i=c-1;i>=0;--i) {
      if(blockErase(throwIdx, i)) return;
    }
  }
}

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
bool dfsRangeChk(int nx, int ny) {
  return (0 <= nx && nx < c && 0 <= ny && ny < r);
}

bool dfsVisited[101][101];
void dfsVisitedClear() {
  for(int i=0;i<r;++i) {
    for(int j=0;j<c;++j) {
      dfsVisited[i][j] = false;
    }
  }
}

bool columnCheckNeeded = false;
int columnList[101];
void clearColumnList() {
  for(int i=0;i<101;++i) {
    columnList[i] = 999999;
  }
}

void dfs(int row, int col) {
  for(int i=0;i<4;++i) {
    int nx = col + dx[i];
    int ny = row + dy[i];
    if(dfsVisited[ny][nx] == false && dfsRangeChk(nx, ny)) {
      if(table[ny][nx] == 'x'){
        if(columnCheckNeeded) {
          columnList[nx] = min(columnList[nx], ny);
        }
        dfsVisited[ny][nx] = true;
        dfs(ny, nx);
      }
    }
  }
}

void pasteRootedResult() {
  for(int i=0;i<r;++i) {
    for(int j=0;j<c;++j) {
      if(dfsVisited[i][j] == true) {
        isrootedCluster[i][j] = true;
      }
    }
  }
}

void rootedClusterCheck() {
  for(int i=0;i<c;++i) {
    if(isrootedCluster[0][i] == false && table[0][i] == 'x') {
      dfsVisitedClear();
      isrootedCluster[0][i] = true;
      dfs(0, i);
      pasteRootedResult();
    } 
  }
}

void findflyCluster(int i, int j) {
  dfsVisitedClear();
  dfsVisited[i][j] = true;
  columnList[j] = i;
  dfs(i, j);
}

int findDownLength() {
  int minLength = 9999999;
  for(int j=0;j<c;++j) {
    if(columnList[j] == 999999) continue;
    for(int i=0;i<r;++i) {
      if(table[i][j] == 'x') {
        if(i == columnList[j]) {
          minLength = min(minLength, i);
          break;
        } else {
          minLength = min(columnList[j] - i - 1, minLength);
        }
      }
    }
  }
  return minLength;
}

void downCluster() {
  int downLength = findDownLength();
  for (int j = 0; j < c; ++j) {
    for (int i = 0; i < r; ++i) {
      if(dfsVisited[i][j] == true) {
        table[i][j] = '.';
        table[i-downLength][j] = 'x';
      }
    }
  }
}

void flyClusterDown() {
  for(int i=0;i<r;++i) {
    for(int j=0;j<c;++j){
      if(isrootedCluster[i][j] == false && table[i][j] == 'x') {
        clearColumnList();
        columnCheckNeeded = true;
        findflyCluster(i, j);
        columnCheckNeeded = false;
        downCluster();
        return;
      }
    }
  }
}

void processing() {
  for(int i=0;i<stickThrowRow.size(); ++i) {
    eraseBlock(stickThrowRow[i]-1, i%2==0);
    rootedClusterCheck();
    flyClusterDown();
    rootedClusterClear();
  }
}

void printAnswer() {
  for(int i=0;i<r;++i) {
    for(int j=0;j<c;++j) {
      cout << table[r-i-1][j];
    }
    cout << '\n';
  }
}

int main(void) {
  // freopen("b2933.txt", "r", stdin);
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  input();
  processing();
  printAnswer();
}