코뚫린 앙드로이드

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";
     }
}

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

3중 포문으로 플로이드 와샬 알고리즘을 사용하였습니다.

전체코드

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

#define INF 1e9
#define MAX_N 101

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, Q;
     cin >> N >> Q;
     for (int i = 0; i <= N; i++) {
          for (int j = 0; j <= N; j++) {
               dp[i][j] = INF;
               dp2[i][j] = INF;
               if (i == j) {
                    dp[i][j] = 0;
                    dp2[i][j] = 0;
               }
          }
     }
     for (int i = 0; i < Q; i++) {
          int a, b; cin >> a >> b;
          dp[a][b] = 1;
          dp2[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]);
               }
          }
     }

     for (int m = 1; m <= N; m++) {
          for (int s = 1; s <= N; s++) {
               for (int e = 1; e <= N; e++) {
                    if (dp2[s][m] != INF && dp2[m][e] != INF)
                         dp2[s][e] = min(dp2[s][e], dp2[s][m] + dp2[m][e]);
               }
          }
     }

     int num = -1;
     for (int i = 1; i <= N; i++) {
          int tmp_ans = 0;
          for (int j = 1; j <= N; j++) {
               if (j == i) continue;
               if (dp[i][j] == INF && dp2[i][j] == INF) tmp_ans++;
          }
          cout << tmp_ans << "\n";
     }
}

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

(다익스트라를 모르신다면 먼저 다익스트라 부터공부 하시는 것을 추천합니다.)

3중 포문으로 모든정점에서 모든정점까지의 최단거리는 다음과 같이 구할 수 있습니다.

(단, 음의 간선이 없을 경우)

(단, 노드의 갯수가 크지 않을경우 O(n^3)...)

     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]);
               }
          }
     }

전체코드

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

#define INF 1e9
#define MAX_N 101

int dp[MAX_N][MAX_N];

int main() {
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int N, Q;
	cin >> N >> Q;
     for (int i = 0; i <= N; i++) {
          for (int j = 0; j <= N; j++) {
               dp[i][j] = INF;
               if (i == j) dp[i][j] = 0;
          }
     }
     for (int i = 0; i < Q; i++) {
          int a, b; cin >> a >> b;
          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]);
               }
          }
     }

     int ans = INF;
     int num = -1;
     for (int i = 1; i <= N; i++) {
          int tmp_ans = 0;
          for (int j = 1; j <= N; j++) {
               if (j == i) continue;
                   tmp_ans += dp[i][j];
          }
          if (tmp_ans < ans) {
               num = i;
               ans = tmp_ans;
          }
     }
     cout << num << "\n";
}

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

문제에서 당신 "벨만포드 알고리즘 아시나요?" 라고 물어본다고 봐도 무방한 문제입니다.

음의 가중치가 존재( 다익스트라 X ) 하고, cycle이 존재한다면 ( 확인가능 : 벨만포드의 특징 )

벨만포드 알고리즘을 알고 있었다면 두 키워드만 보고 풀이가 떠올라야 벨만포드 알고리즘의 특성을 잘 알 고있는 것이고, 몰랐다면 이번문제로 연습하고 다른 문제들도 풀어 보는게 좋을 것 같습니다. 코드에 주석으로 어떤형식으로 작동하는지 코멘트 해놓았습니다. 

전체코드

#include <iostream>
#include <vector>
#include <limits.h>
#define INF INT_MAX
using namespace std;
vector<pair<int,int>> vec[502];
int dist[502];
int main() {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int N, M;
     cin >> N >> M;

     fill(dist, dist + N + 1, INF);

     for (int i = 0; i < M; i++) {
          int A, B, C;
          cin >> A >> B >> C;
          vec[A].push_back({ B,C });
     }

     dist[1] = 0;
     bool cycle = false;

     // V-1 + 1( 음의사이클 판단 ) = V번 반복
     for (int i = 1; i <= N; i++) { // (N-1) 까지는 최단거리 계산 ,N번째는 음의사이클 여부 판단
          // 모든 시작정점 에대해서
          for (int j = 1; j <= N; j++) {
               // 모든 시작정점의 간선에 대해서
               for (const auto & x : vec[j]) {
                    int next = x.first, d = x.second;
                    if (dist[j] != INF && dist[next] > dist[j] + d) {
                         dist[next] = dist[j] + d;
                         // i == N일때 변화가 생겼다 -> 음의사이클로인해 무한으로 갱신된다
                         if (i == N) cycle = true;
                    }
               }
          }
     }
     if (cycle) cout << -1 << "\n";
     else {
          for (int i = 2; i <= N; i++) {
               if (dist[i] == INF) cout << -1 << "\n";
               else cout << dist[i] << "\n";
          }
     }


}