코뚫린 앙드로이드

https://www.acmicpc.net/problem/10774

문제해설

이 문제의 분류가 Disjoint-set 인데 , 진짜 일차원적인 Disjoint-set 인문제같습니다.

그냥 if로 경우 잘나누면 되는 문제입니다.

전체코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;

#define MAX_J 1000000
char arr[MAX_J + 1];

int main() {
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
     int J; cin >> J;
     int A; cin >> A;
     for (int i = 1; i <= J; i++) {
          cin >> arr[i];
     }
     int ans = 0;
     for (int i = 0; i < A; i++) {
          char tag; int num;
          cin >> tag >> num;
          if (arr[num] == 'S') {
               if (tag == 'S') {
                    arr[num] = 'X';
                    ans++;
               }
          }
          else if (arr[num] == 'M') {
               if ( tag == 'M' || tag == 'S') {
                    arr[num] = 'X';
                    ans++;
               }
          }
          else if (arr[num] == 'L') {
               if (tag == 'L' || tag == 'M' || tag == 'S') {
                    arr[num] = 'X';
                    ans++;
               }
          }
     }
     cout << ans << "\n";
}

https://www.acmicpc.net/problem/5012

문제해설

"펜윅 트리"를 사용하여 풀었습니다.

이 문제는 밑의 문제와 굉장히 유사한 문제라고 할 수 있습니다.

2019/10/06 - [알고리즘/BOJ] - [백준BOJ] 3006 터보소트

i < j < k 이면서 Ai > Aj > Ak

인 경우의 수를 찾기 위해서는

j를 기준으로 왼쪽, 오른쪽을 탐색하면 됩니다.

< 변수 >

#define MAX_N 100000
int tree_left[MAX_N + 1];
int tree_right[MAX_N + 1];
vector<int> l, r;

case1 : 자신 기준 왼쪽에 있으면서 큰 값의 수

case2 : 자신 기준 오른쪽에 있으면서 작은 값의 수

< case1 >

int left =  query(tree_left, MAX_N) - query(tree_left, data_left);

위의 코드처럼 구간합으로 자신보다 왼쪽에 있으면서 큰 값들의 갯수를 구할 수 있습니다.

< case2 >

int right =  query(tree_right,  data_right-1);

위의 코드처럼 구간합으로 자신보다 오른쪽에 있으면서 작은 값들의 갯수를 구할 수 있습니다. 

전체코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
vector<int> vec;
#define MAX_N 100000
int tree_left[MAX_N + 1];
int tree_right[MAX_N + 1];
vector<int> l, r;

void update(int tree[],int target, int value) {
     while (target <= MAX_N) {
          tree[target] += value;
          target += (target & -target);
     }
}

int query(int tree[],int target) {
     int ret = 0;
     while (target >= 1) {
          ret += tree[target];
          target -= (target &-target);
     }
     return ret;
}

int main() {
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
     int N;
     cin >> N;
     for (int i = 1; i <= N; i++) {
          int data; cin >> data;
          vec.push_back(data);
     }

     long long ans = 0;
     for (int i = 0, j = vec.size()-1; i < vec.size(); i++, j--) {
          int data_left = vec[i]; 
          int data_right = vec[j];

          int right =  query(tree_right,  data_right-1);
          int left =  query(tree_left, MAX_N) - query(tree_left, data_left);
          l.push_back(left); r.push_back(right);

          update(tree_right, data_right, 1);
          update(tree_left, data_left, 1);

     }
     for (int i = 0, j = r.size()-1; i < l.size(); i++,j--) {
          ans += ((long long)l[i] * r[j]);
     }
     cout << ans << "\n";
}

https://www.acmicpc.net/problem/3006

문제해설

정답률이 무려 70% 라서 여러풀이가 가능한 것 같습니다. 저는 "펜윅 트리"를 사용한 풀이를 해설 하도록 하겠습니다.

     for (int i = 1; i <= N; i++) {
          int data; cin >> data;
          update(i, 1);
          pos[data] = i;
     }

update는 위와같이 단지 자리를 1로 update 해주었고,

해당 data가 어느위치에 삽입되었는지 pos 배열에 저장 해주었습니다.

     for (int i = 1, j = N; i <= j; i++,j--) {
          int minPos = pos[i];
          int maxPos = pos[j];
          cout << query(minPos-1) << "\n";
          update(minPos, -1);
          if (i != j) {
               cout << query(N) - query(maxPos) << "\n";
               update(maxPos, -1);
          }
     }

제일작은값(1...)

제일 큰값(N...)

처리를 위해서 i++, j--를 이용함과 동시에 같다면 하나의 인덱스만 처리하고 반복문을 종료 하였습니다.

위의 코드는 해당 숫자보다 앞에 있는 숫자의 갯수를 출력하고

해당 숫자는 자기 자리를 찾아가게 되었으니 -1로 update처리 해주었습니다.

전체코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;

#define MAX_N 100000
int tree[MAX_N + 1];
int pos[MAX_N + 1];

void update(int target, int value) {
     while (target <= MAX_N) {
          tree[target] += value;
          target += (target & -target);
     }
}

int query(int target) {
     int ret = 0;
     while (target >= 1) {
          ret += tree[target];
          target -= (target &-target);
     }
     return ret;
}

int main() {
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
     int N; cin >> N;

     for (int i = 1; i <= N; i++) {
          int data; cin >> data;
          update(i, 1);
          pos[data] = i;
     }

     for (int i = 1, j = N; i <= j; i++,j--) {
          int minPos = pos[i];
          int maxPos = pos[j];
          cout << query(minPos-1) << "\n";
          update(minPos, -1);
          if (i != j) {
               cout << query(N) - query(maxPos) << "\n";
               update(maxPos, -1);
          }
     }
}

https://www.acmicpc.net/problem/1280

문제해설

"펜윅 트리" 를 사용하여 풀었습니다.  입력이 들어왔을때 두가지의 경우를 나누었습니다.

현재 input 이 x 라고 하였을때

case1 : x 보다 좌표값이 큰 나무들

case2 : x 보다 좌표값이 작은 나무들

<  case1  >

x보다 작은 값들과의 합은

(x - a) + (x - b) + (x - c) = 3*x - (a + b + c)

즉, (입력보다 작은 점들의 갯수) * (입력좌표) - ( 입력보다 작은 점들의 합 )

으로 나타낼 수 있습니다.

< case2 >

x보다 큰 값들의 합은

(a - x) + (b - x) + (c - x) = (a + b + c) - 3*x

즉,(입력보다 큰 점들의 합) - (입력보다 큰 점들의 갯수) * (입력좌표)

로 나탈낼 수 있습니다.

두가지의 경우를 나누어서

펜윅트를 사용해서

입력좌표보다 큰 값들의 총 갯수, 총 합

입력좌표보다 작은 값들의 총 갯수, 총 갯수

를 구한뒤 문제를 풀 수 있습니다.

(다만 주의할점은,  중간 계산 과정에서 long long 범위에 담기지 않을 수 있음으로, mod 연산을 중간 과정에서도 해줘야합니다 )

전체코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <set>
using namespace std;

#define MAX_N 200000
#define DIV 1000000007
typedef long long ll;
ll tree_dist[MAX_N+1];
int tree_cnt[MAX_N+1];
int N;

void update_dist(int target, int value) {
     while (target <= MAX_N) {
          tree_dist[target] += value;
          target += (target & -target);
     }
}

void update_cnt(int target, int value) {
     while (target <= MAX_N) {
          tree_cnt[target] += value;
          target += (target & -target);

     }
}

ll query_dist(int target) {
     ll ret = 0;
     while (target >= 1) {
          ret += tree_dist[target];
          target -= (target & -target);
     }
     return ret;
}
int query_cnt(int target) {
     int ret = 0;
     while (target >= 1) {
          ret += tree_cnt[target];
          target -= (target & -target);
     }
     return ret;
}

int main() {
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
     int N; cin >> N;
     ll ret = 1;
     for (int i = 1; i <= N; i++) {
          ll tmp = 0;
          int data; cin >> data; data++;
          if (i == 1) {
               update_cnt(data, 1);
               update_dist(data, data);
          }
          else {
               tmp = (tmp + (query_cnt(data - 1) * data) - (query_dist(data - 1))) % DIV;
               tmp = (tmp + (query_dist(MAX_N) - query_dist(data)) - (query_cnt(MAX_N) - query_cnt(data)) * data) % DIV;;
               update_cnt(data, 1);
               update_dist(data, data);
               ret = (ret * tmp) % DIV;
          }
       
     }
     cout << ret % DIV << "\n";

}

https://www.acmicpc.net/problem/11658

문제해설

"펜윅 트리"를 이용한 풀이가 가능합니다. "펜윅 트리"에 대해서 아직 모르시는 분들은 아래링크를 보고 공부하시면 될 것 같습니다.

https://www.acmicpc.net/blog/view/21

 < update, query 함수 >

//변수
#define MAX_N 1025
int tree[MAX_N][MAX_N];
int tree_data[MAX_N][MAX_N];
int N, M, totalN;

void update_tree(int row,int col, int value) {
     while (col <= N) {
          tree[row][col] += value;
          col += (col & -col);
     }
}

int query(int row, int col) {
     int ret = 0;
     while (col >= 1) {
          ret += tree[row][col];
          col -= (col & -col);
     }
     return ret;
}

update는 해당 row에 대해서 해주면 됩니다.

query또한 해당 row에 대해서 리턴 해주시면 됩니다.

( 처음엔 tree[MAN_N * MAX_N] 일차원 배열을 사용했는데 시간초과가 나더군요 ㅠㅠ..)

전체코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;

//변수
#define MAX_N 1025
int tree[MAX_N][MAX_N];
int tree_data[MAX_N][MAX_N];
int N, M, totalN;

void update_tree(int row,int col, int value) {
     while (col <= N) {
          tree[row][col] += value;
          col += (col & -col);
     }
}

int query(int row, int col) {
     int ret = 0;
     while (col >= 1) {
          ret += tree[row][col];
          col -= (col & -col);
     }
     return ret;
}

int main() {
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
      cin >> N >> M;
     for (int i = 1; i <= N; i++) {
          for (int j = 1; j <= N; j++) {
               int data; cin >> data;
               tree_data[i][j] = data;
               update_tree(i, j, data);
          }
     }
     for (int i = 0; i < M; i++) {
          int tag; cin >> tag;
          if (tag == 0) {
               int row, col, value, diff;
               cin >> row >> col >> value;
               diff = value - tree_data[row][col];
               update_tree(row,col, diff);
               tree_data[row][col] = value;
          }
          else {
               int row1, col1, row2, col2;
               int ans = 0;
               cin >> row1 >> col1 >> row2 >> col2;
               for (int j = row1; j <= row2; j++) {
                    int ret2 = query(j, col2);
                    int ret1 = query(j,col1-1);
                    ans += ret2 - ret1;
               }
               cout << ans << "\n";
          }
     }
}

https://www.acmicpc.net/problem/1507

플로이드를 잘 이해하고 있다면 쉽게 풀 수있는 문제이고, 그렇지 않다면 다소 어려울 수 있는 문제입니다.

플로이드 알고리즘을 사용해서 어떤 map[N][N] 배열을 만들었다면 만들어짐 map 배열의 특징은

(s -> m -> e) = (s -> e)

의 특징을 띄게 됩니다.

때문에 완성된 map배열의 s->e 경로는 s -> m -> e 로 똑같은 결과가 나오기 떄문에

없어도 되는 경로라고 할 수 있습니다.

-1의 출력( 불가능한 경우 )는 민호가 map 배열을 잘못 만들었을 경우가 해당합니다.

전체코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;

#define MAX_N 21
#define INF 1e9
int dp[MAX_N][MAX_N];
int dp2[MAX_N][MAX_N];

int main() {
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
     int N; cin >> N;
     for (int i = 0; i < N; i++) {
          for (int j = 0; j < N; j++) {
               int data; cin >> data;
               dp[i][j] = data; // 민호가 만든 최솟값
               dp2[i][j] = data; // 민호가 만든 최솟값으로 만들 수 있는 최솟값
          }
     }

     for (int m = 0; m < N; m++) {
          for (int s = 0; s < N; s++) {
               for (int e = 0; e < N; e++) {
                    if (s == m || e == m) continue; // s -> m -> e 인경우에 m는 s와 e와 달라야 유효한 비교가 된다.
                    if (dp[s][e] == dp[s][m] + dp[m][e]) { 
                         // 중간 지점을 거쳐갔을때와 바로 갔을 때 같다면
                         // 바로 가는 길을 없는길로 처리 해준다
                         dp2[s][e] = 0;
                    }
                    else if (dp[s][e] > dp[s][m] + dp[m][e]){
                         // 바로 가는길이 중간 지점을 거쳐오는 거보다 오래 걸리는 경우는
                         // 민호가 dp table을 잘못 만든 경우이다.
                         cout << -1 << "\n";
                         return 0;
                    }

               }
          }
     }
     int total = 0;
     // [i][j] = [j][i] 이므로 대각기준 오른쪽만 더해준다.
     for (int i = 0; i < N; i++) {
          for (int j = i + 1; j < N; j++) {
               total += dp2[i][j];
          }
     }
     cout << total << "\n";


}

https://www.acmicpc.net/problem/2660

플로이드 와샬 알고리즘을 사용해서 3중포문으로 dp table을 생성한뒤에

문제 조건만 잘 따져가면 쉽게 풀 수 있습니다.

전체코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;

#define MAX_N 51
#define INF 1e9
int dp[MAX_N][MAX_N];

int main() {
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
     int N,a,b; cin >> N;
     for (int i = 1; i <= N; i++) {
          for (int j = 1; j <= N; j++) {
               if (i == j) dp[i][j] = 0;
               else dp[i][j] = INF;
          }
     }
     while (cin >> a >> b) {
          if (a == -1 && b == -1) break;
          dp[a][b] = 1;
          dp[b][a] = 1;
     }

     for (int m = 1; m <= N; m++) {
          for (int s = 1; s <= N; s++) {
               for (int e = 1; e <= N; e++) {
                    if (dp[s][m] != INF && dp[m][e] != INF) {
                         dp[s][e] = min(dp[s][e], dp[s][m] + dp[m][e]);
                    }
               }
          }
     }
     vector<int> ans;
     int mmin = 1e9;
     for (int i = 1; i <= N; i++) {
          int tmp_max = -1;
          for (int j = 1; j <= N; j++) {
               tmp_max = max(tmp_max, dp[i][j]);
          }
          if (mmin == 1e9) {
               mmin = tmp_max;
               ans.push_back(i);
          }
          else {
               if (mmin < tmp_max) continue;
               else if (mmin == tmp_max) ans.push_back(i);
               else {
                    ans.clear();
                    mmin = tmp_max;
                    ans.push_back(i);
               }
          }
     }
     cout << mmin << " " << ans.size() << "\n";
     for (const auto & x : ans) {
          cout << x << " ";
     }
     cout << "\n";
}

https://www.acmicpc.net/problem/9205

입력 제한 조건이 최대 100밖에 들어오지 않습니다. O(n^2)로 대부분 가능한 풀이라는걸 생각하며 문제를 읽었습니다.

(0 ≤ n ≤ 100).

좌표계로 노드의 위치가 들어오기 때문에 처음엔 좌표압축을 해야하나 싶었지만,

필요한 정보는 어떤 한 정점에서 어떤 정점으로 갈 수 있는가? 를 알면 되고

한 정점에서 다른 정점으로 갈 조건은 비용(맥주)를 20병 이하로 먹는 길이 맨해튼 거리가 1000이하면 됩니다.

밑의 코드는 한 정점에서 맨해튼 거리가 1000이하인 정점을 인접노드로 push_back 하는 코드입니다.

        for (int i = 0; i < vec.size(); i++) {
               for (int j = 0; j < vec.size(); j++) {
                    if (i == j) continue;
                    int cost;
                    if ((abs(vec[i].first - vec[j].first) + abs(vec[i].second - vec[j].second)) % 50 == 0)
                         cost = (abs(vec[i].first - vec[j].first) + abs(vec[i].second - vec[j].second)) / 50;
                    else
                         cost = (abs(vec[i].first - vec[j].first) + abs(vec[i].second - vec[j].second)) / 50 + 1;

                    if (cost <= 20) {
                         map[i].push_back(j);
                    }
               }
          }

이후에, DFS를 통해 N+1번정점( 페스티발 )을 방문할 수 있는지만 체크하면 됩니다.

전체코드

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

vector<pair<int, int> > vec;

bool visit[103];
vector<int> map[103];

void dfs(int now) {
     visit[now] = true;
     for (int i = 0; i < map[now].size(); i++) {
          if (visit[map[now][i]] == false) {
               dfs(map[now][i]);
          }
     }
}

int main() {
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
     int t; cin >> t;
     while (t--) {
          int n, x, y; cin >> n;
          // 초기화
          for (int i = 0; i <= n + 2; i++) {
               map[i].clear();
               visit[i] = false;
          }
          vec.clear();

          // 입력
          for (int i = 0; i < n+2; i++) {
               int x, y; cin >> x >> y;
               vec.push_back({ x,y });
          }

          // O(n^2)으로 모든정점에서 모든정점까지 비용 update
          for (int i = 0; i < vec.size(); i++) {
               for (int j = 0; j < vec.size(); j++) {
                    if (i == j) continue;
                    int cost;
                    if ((abs(vec[i].first - vec[j].first) + abs(vec[i].second - vec[j].second)) % 50 == 0)
                         cost = (abs(vec[i].first - vec[j].first) + abs(vec[i].second - vec[j].second)) / 50;
                    else
                         cost = (abs(vec[i].first - vec[j].first) + abs(vec[i].second - vec[j].second)) / 50 + 1;

                    if (cost <= 20) {
                         map[i].push_back(j);
                    }
               }
          }

          // DFS
          // 0번노드 : 집의 위치
          // N+1번노드 : 페스티발의 위치
          dfs(0);
          if (visit[n + 1] == true) cout << "happy\n";
          else cout << "sad\n";
     }
}