푸키키키

문제 이해

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

평범한 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/15661

풀이

void makePossibleCase() {
  for(int depth=1;depth<=n/2;++depth) {
    dfs(0, 0, depth);
  }
}

void processing() {
  input();
  makePossibleCase();
  cout << ans << endl;
}

makePossibleCase();

문제를 해결하기 위해서 경우의 수를 만들어 내야한다. 경우의 수는 한팀이 2명이상이 되도록 팀을 구성해야 한다. 한 팀에 만약 2명을 배정해줬다면 나머지가 다 다른 팀으로 가게 되므로 다른 팀에 n-2가 배정된다. 이런식으로 3이면 n-3 ... 으로 한팀에 n/2까지만 할당한 경우까지 진행하면 풀어낼 수 있다.

아래는 depth≤n/2, 위는 depth<n이다. 눈에띄게 시간차이가 난다.

경우의 수 만들어내기 - dfs활용

bool visited[21];
void dfs(int depth, int nowidx, int maxDepth) {
  if(depth == maxDepth) {
    checkTeamScore();
    return;
  }

  for(int i=nowidx;i<n;++i) {
    if(visited[i] == false) {
      visited[i] = true;
      oneCase.push_back(i);
      dfs(depth+1, i+1, maxDepth);
      oneCase.pop_back();
      visited[i] = false;
    }
  }
}

• oneCase : 한 팀을 구성하는 index가 담길 vector

한팀에 배정할 팀원 수가 될 때까지 경우의 수를 만들어낸다. visited를 통해 이미 뽑아낸 것은 다시 뽑지 않도록 하고 nowidx를 통해 이미 뽑은 index보다 작은 값은 뽑지 않도록 해서 조합을 구현했다. 원하는 만큼 팀원을 뽑았다면 checkTeamScore()를 통해 답을 구해낸다.

checkTeamScore();

int ans = 999999;
void checkTeamScore() {
  leftTeamIdxClear();
  for(int j=0;j<oneCase.size();++j) {
    leftTeamIdx[oneCase[j]] = true;
  }
  ans = min(ans, calTeamScore());
}

왼쪽 팀에 배정된 인덱스들을 leftTeamIdx에 체크해준다. 이 값을 통해 왼쪽팀과 오른쪽 팀을 나누게 된다. 체크해준 후 calTeamScore()를 통해 두 팀의 각 값을 계산해내고 ans를 최신화해준다.

calTeamScore();

int calTeamScore() {
  int leftScore = 0;
  int rightScore = 0;
  for(int i=0;i<n;++i) {
    for(int j=i+1;j<n;++j) {
      if(leftTeamIdx[i] && leftTeamIdx[j]) {
        leftScore += table[i][j];  
      }
      if(!leftTeamIdx[i] && !leftTeamIdx[j]) {
        rightScore += table[i][j];  
      }
    }
  }

  return abs(leftScore - rightScore);
}

for문 두 개를 돌면서 두 인덱스가 모두 왼쪽 팀이면 그 값을 leftScore에, 둘다 오른쪽 팀이면 rightScore에 더하도록 했다. n제한이 20이므로 n^2 시간복잡도가 큰 부담이 없다.

코드

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

using namespace std;

/*
  인원수 달라도 됨
  1. 뽑는 경우의 수 생성
  2. 팀 만들어서 차이 보기
  - 반복
*/
int table[21][21];
int n;

void scorePreprocessing() {
  for(int i=0;i<n;++i) {
    for(int j=i+1;j<n;++j) {
      table[i][j] += table[j][i];
    }
  }
}

void input() {
  cin >> n;
  for(int i=0;i<n;++i) {
    for(int j=0;j<n;++j) {
      cin >> table[i][j];
    } 
  }
  scorePreprocessing();
}

vector<vector<int> > cases;
vector<int> oneCase;

bool leftTeamIdx[21];
void leftTeamIdxClear() {
  memset(leftTeamIdx, false, sizeof(leftTeamIdx));
}

int calTeamScore() {
  int leftScore = 0;
  int rightScore = 0;
  for(int i=0;i<n;++i) {
    for(int j=i+1;j<n;++j) {
      if(leftTeamIdx[i] && leftTeamIdx[j]) {
        leftScore += table[i][j];  
      }
      if(!leftTeamIdx[i] && !leftTeamIdx[j]) {
        rightScore += table[i][j];  
      }
    }
  }

  return abs(leftScore - rightScore);
}

int ans = 999999;
void checkTeamScore() {
  leftTeamIdxClear();
  for(int j=0;j<oneCase.size();++j) {
    leftTeamIdx[oneCase[j]] = true;
  }
  ans = min(ans, calTeamScore());
}

bool visited[21];
int recodeDepth = 0;
void dfs(int depth, int nowidx, int maxDepth) {
  if(depth == maxDepth) {
    if(recodeDepth != depth) {
      recodeDepth = depth;
    }
    checkTeamScore();
    return;
  }

  for(int i=nowidx;i<n;++i) {
    if(visited[i] == false) {
      visited[i] = true;
      oneCase.push_back(i);
      dfs(depth+1, i+1, maxDepth);
      oneCase.pop_back();
      visited[i] = false;
    }
  }
}

void makePossibleCase() {
  for(int depth=1;depth<=n/2;++depth) {
    dfs(0, 0, depth);
  }
}

void processing() {
  input();
  makePossibleCase();
  cout << ans << endl;
}

int main() {
  processing();
}