푸키키키

문제

https://app.codility.com/programmers/lessons/15-caterpillar_method/min_abs_sum_of_two/

풀이

1. 입력 배열을 정렬한다.
2. 배열의 양 끝 값의 합부터 시작해서 점점 배열의 안쪽으로 들어가며 계산한다.
   • 양 끝 값의 합을 구하고 둘 중 절댓값이 큰 값의 Index를 한칸 안쪽으로(시작 index는 +1, 끝 index는 -1) 보낸다.
3. 두 index가 같아졌을 때 계산을 종료하고 이 때의 index가 가리키는 값이 절대값이 가장 작은 원소이므로 이 값의 2배의 절대값도 정답의 후보다.

문제 이해

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

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

풀이

1. 만들 수 있는 각도로 새로운 각도를 만들어 set에 넣는다.
2. set에 있는 원소를 vector에 넣은 다음 2중 for문을 통해 만들 수 있는 모든 각도를 만든 후 다시 set에 넣는다.
3. 반복하다가 set의 크기와 vector의 크기가 같아지면 더 이상 추가될 게 없다는 것이므로 이 때 set에 현우가 외친 각이 있으면 YES, 없으면 NO

코드

#include <iostream>
#include <set>
#include <vector>

using namespace std;

int n, k;
vector<int> angle;
vector<int> output;
void input() {
  cin >> n >> k;
  int temp;
  for(int i=0;i<n;++i) {
    cin >> temp;
    angle.push_back(temp);
  }
  for(int i=0;i<k;++i) {
    cin >> temp;
    output.push_back(temp);
  }
}

int convert(int num) {
  if(num >= 360) {
    return num - 360;
  }
  if(num < 0) {
    return num + 360;
  }
  return num;
}

set<int> ans;
void process() {
  int nowAnsLength = 0; 
  for(int i=0;i<angle.size(); ++i) {
    ans.insert(convert(angle[i]));
  }
  for(int i=0;i<angle.size(); ++i) {
    for(int j=0;j<angle.size(); ++j) {
      ans.insert(convert(angle[i] + angle[j]));
      ans.insert(convert(angle[i] - angle[j]));
    }
  }
  while(nowAnsLength != ans.size()) {
    nowAnsLength = ans.size();
    vector<int> temp_vec;
    for(auto x : ans) {
      temp_vec.push_back(x);
    }
    for(int i=0;i<temp_vec.size(); ++i) {
      for(int j=0;j<temp_vec.size(); ++j) {
        ans.insert(convert(temp_vec[i] + temp_vec[j]));
        ans.insert(convert(temp_vec[i] - temp_vec[j]));
      }
    }
  }
  for(int i=0;i<output.size();++i) {
    if(ans.count(output[i]) == 0) {
      cout << "NO" << endl;
    } else {
      cout << "YES" << endl;
    }
  }
  return;
}

int main(void) {
  input();
  process();
}