BEEZI life

14889번: 스타트와 링크

위의 문제로 예를 들어서,

n명의 선수가 있고, 0번팀과 1번팀으로 선수들을 나눠서, 0번팀의 능력치합과 1번팀의 능력치합을 계산해야 하는 상황이다.
이 때, permutation을 사용하기 위해서 team=[0,1,1,0,...,1]이라고 하고,

n*n의 반복문을 돌면서 i와 j가 같은 팀일 때 각 팀의 능력치에 더해준다고 하면
\(O(n^2)\)의 시간복잡도를 가지게 된다.

int calcgap(){
  int team0=0, team1=0;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if(i==j) continue;
      // mask[i]에는 i의 팀 번호가 저장되어있다.
      if(mask[i]==0 && mask[j]==0) {team0+=stat[i][j]; continue;} 
      if(mask[i]==1 && mask[j]==1) {team1+=stat[i][j]; continue;}
    }
  }
  return abs(team0-team1);
}

이번에는 0번팀과 1번팀을 각각의 vector<int>에 담은다음 각 팀에서 반복문을 돌면서 능력치를 구한다면

\( O((\frac{n}{2})^{2}*2)=O(\frac{n^2}{2}) \) 의 시간복잡도를 가지게 된다.

그 이유는 수식에서 찾아볼 수 있다.

int calcgap(){
  vector<int> team0, team1;
  for(int i=0; i<n; i++){
    if(mask[i]==0) team0.push_back(i);
    else team1.push_back(i);
  }
  int gap=0;
  for(int i=0; i<n/2; i++){
    for(int j=i+1; j<n/2; j++){
      int a=team0[i], b=team0[j];
      gap+=stat[a][b];
      gap+=stat[b][a];
    }
  }
  for(int i=0; i<n/2; i++){
    for(int j=i+1; j<n/2; j++){
      int a=team1[i], b=team1[j];
      gap-=stat[a][b];
      gap-=stat[b][a];
    }
  }
  return abs(gap);
}

실제로 시간이 절반정도로 줄어든 것을 확인할 수 있다.

http://blog.naver.com/PostView.nhn?blogId=jinhan814&logNo=222202200887&parentCategoryNo=6&categoryNo=&viewDate=&isShowPopularPosts=false&from=postView

https://jacking75.github.io/C-_array_ref/

이 문제를 풀 때 쉽게 생각할 수 있는 풀이는

음수*음수->양수
양수*양수->양수

이렇게 묶어서 합을 최대로 만드는것이다.

조금 더 생각하면,
음수의 개수가 홀수개일 때,
-3, -2, -1 을 (-3 * -2) + -1로 묶을 수 있다.
여기서 0이 1개이상일경우
-3, -2, -1, 0을 (-3 * -2) + (-1 * 0)로 묶어서 -1을 없애줄 수 있다.

여기까지는 생각하기 쉽지만 한가지 간과한 것이 있다.

1은 무엇과 곱해도 손해이다. 무조건 더하는것이 낫다.
4, 3, 2, 1-> (4 * 3) + (2 * 1) = 14
                 -> (4 * 3) + 2 + 1 = 15

0과 함께 있는 경우에도 마찬가지이다.
4, 3, 1, 0-> (4 * 3) + (1 * 0) = 12
                 -> (4 * 3) + 1 + 0 = 13

이 문제를 [백준 1202] 보석도둑에서의 lower_bound를 이용한 풀이와 비슷하게 시도해보고자 한다.

lower\_bound(x): x이상의 수 중 최솟값 인데

순회강연의 문제에서는 각 강연의 endline이 주어지고, 그 endline안에만 강연을 할 수 있다.

즉 day=2일때, endlined이 2이하인 강연만 할 수 있어서 정확히 lower_bound의 정의에 반대이다.

여기서 중요한것이 정확히 lower_bound의 반대라는 점인데,

그렇다면 각 케이스에서 가장 큰 endline을 maxEndline이라고 했을 때,

endline = maxEndline - endline;

이 상태에서는 "lower_bound(x'): x'이하의 수중 최댓값"이 된다.

따라서, day=2일때, lower_bound(day)의 결과는 endline이 2 이하인 강연 중 비용이 가장 큰 것의 index가 나오게 된다.

이 풀이는 뭔가 머릿속으로는 이해가 되는데, 말로 하려니깐 정의자체가 어려운것같다.

#include <bits/stdc++>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vpii;

// INT_MAX = 2^31 ~= 2.1e9
// LLONG_MAX = 2^63 ~= 9.2e18

const int MAX=(int)1e4;
pii lecture[MAX+5]; // <비용, 기간>
multiset<int> day;

int main(){
  int n;
  scanf("%d", &n);

  int nDay=0;
  for(int i=0; i<n; i++){
    scanf("%d %d", &lecture[i].first, &lecture[i].second);
    if(lecture[i].second>nDay) nDay=lecture[i].second;
  }
  for(int i=0; i<n; i++){
    lecture[i].second=nDay-lecture[i].second;
  }
  for(int i=0; i<nDay; i++) day.insert(i);

  sort(lecture, lecture+n, greater<pii>()); // 비용이 큰 순으로 정렬을 한다.

  ll answer=0;
  for(int i=0; i<n; i++){ // i는 강연의 순번, 비용이 높은것이 먼저 나온다.
    auto iter=day.lower_bound(lecture[i].second);
    if(iter!=day.end()){
      // 값을 찾았다면 비용을 더해주고, 해당 날은 제거한다.
      answer+=lecture[i].first;
      day.erase(iter);
    }
  }
  printf("%lld", answer);
  return 0;
}

ps에서 c++을 사용하는 사람들 중 입력을 받을 때, 'cin'으로 입력을 받는 사람들은 대부분 시간을 단축하기 위해서

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
}

이런 trick을 사용한다.

하지만 문제를 푸는 도중에 문제의 입력을 색다른 방법으로 받아야 할 때가 있다.

위와 같은 경우들인데, 각 cell의 숫자들이 연속해서 입력되고 있다.

이것을 입력받기 위해서는 여러 가지 방법을 사용할 수 있는데,

내가 간단하게 사용하는 방법은 한자리씩 int형으로 입력받는 방법이다.

scanf("%1d", &a[x][y]);

이렇게 scanf를 사용하면서도 위의 trick을 지우지 않고 cin을 사용한다면 입력을 받을 때 오류가 발생한다.

이것 때문에 틀리지 않아도 되는 문제를 여러 번 틀렸다.

결론은, scanf를 사용할 때에

ios_base::sync_with_stdio(false);

이것은 꼭 주석처리 해 주어야 한다.

test-case가 주어지는 문제를 풀 때 가끔씩 전역변수로 선언된 vector을 케이스마다 새롭게 사용해야 하는 경우가 있다.

#include<bits/stdc++.h>
vector<int> a(20001);
...
int main(){
  ...
  int t;
  cin>>t;
  while(t--){
    ...
    for(int i=0; i<n; i++){
      cin>>a[i];
    }
    ...
  }
  ...
}
    

위의 경우와 같이 전역변수 vector<int> a에 test-case마다 새로 값을 입력받아야 할 때에는,

test-case가 끝날 때 마다 전역변수 a의 값들을 초기화해주어야 한다.

이럴 때 자주 사용하는것은 

a.clear()

이것일 것이다.

하지만 

codingdog.tistory.com/entry/c-vector-clear-size를-0으로-만들어-준다

이 블로그의 글에 따르면 완벽하게 초기화 되지 않는다.

이것을 보완하여 완벽한 초기화를 하기 위해서

swap trick을 사용해주면 된다. 위의 예시를 활용해보자면

#include<bits/stdc++.h>
vector<int> a(20001);
...
int main(){
  ...
  int t;
  cin>>t;
  while(t--){
    ...
    for(int i=0; i<n; i++){
      cin>>a[i];
    }
    ...
    vector<int>(20001).swap(a);
  }
  ...
}
    

만약 이차원 vector라도 동일하게 사용해주면 된다.

#include<bits/stdc++.h>
vector< vector<int> > a(20001);
...
int main(){
  ...
  int t;
  cin>>t;
  while(t--){
    ...
    for(int i=0; i<n; i++){
      cin>>a[i];
    }
    ...
  }
  ...
  vector< vector<int> >(20001).swap(a);
}
    

int main(){
    int arr[1025][1025]={0,};
    int d[1025][1025]={0,};
    
    ...
    
    for(int i=1; i<=n; i++){
      for(int j=1; j<=n; j++){
      	d[i][j]=10 // 상수대입
        d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+arr[i][j]; // dp연산
      }
    }
    
    ...
}

main함수에서 arr배열과 d배열을 모두 1025*1025*sizeof(int)의 크기로 선언을 한 뒤

두 배열에 모두 값을 할당할 때, 

d[i][j]=10과 같이 상수를 대입했을 때에는 오류가 없었지만

d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+arr[i][j]; 와 같이 dp연산을 했을 때에는 segmentation fault가 발생하였다.

d배열을 전역변수에 선언하고 dp연산을 했을 때에는 오류가 발생하지 않는것으로 보아서

이 상황에서 오류가 발생한 원인은 매우 큰 두개의 지역변수로 인해서 스택메모리가 초과하여 발생한 오류로 보인다.

앞으로는 매우 큰 배열변수를 선언할 때에는 전역변수에 선언하는게 나을 것 같다.