#include <cstdio>
/**
* https://www.acmicpc.net/problem/2010
* BOJ 백준온라인져지 2010 플러그 풀이
*/
int main () {
long long result = 0;
int testcase = 0;
scanf("%d", &testcase);
while (testcase--) {
int temp = 0;
scanf("%d", &temp);
result += temp - 1;
}
printf("%lld", result + 1);
}
view raw BOJ_2010.cpp hosted with ❤ by GitHub

문제

선영이의 집에는 콘센트를 꽂을 수 있는 플러그가 하나밖에 없다. 선영이는 많은 컴퓨터를 가지고 있는데, 컴퓨터의 전원 문제는 어떻게 해결하는 것일까?

하나의 플러그가 있고, N개의 멀티탭이 있다. 각 멀티탭은 몇 개의 플러그로 이루어져 있다고 한다. 최대 몇 대의 컴퓨터를 전원에 연결할 수 있을까?

입력

첫째 줄에 멀티탭의 개수 N이 주어진다. (1<=N<=500,000) 이어서 둘째 줄부터 N개의 줄에 걸쳐 각 멀티탭이 몇 개의 플러그를 꽂을 수 있도록 되어 있는지를 나타내는 자연수가 주어진다. 이 자연수는 1,000을 넘지 않는다.

출력

첫째 줄에 최대로 전원에 연결될 수 있는 컴퓨터의 수를 출력한다.


저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 5567 결혼식 풀이  (0) 2018.02.17
BOJ 백준온라인져지 1076 저항 풀이  (0) 2018.02.17
BOJ 백준온라인져지 3046 R2 풀이  (0) 2018.02.15
BOJ 백준온라인져지 4963 섬의 개수 풀이  (0) 2018.02.13
BOJ 백준온라인져지 11004 K번째 수 풀이  (0) 2018.02.10

1. R1/2 + R2/2 = S (기본식)

2. R1/2 - S = -R2/2 (이항)

3. R2=2S-R1 (더 간단한 식)

#include <cstdio>
/**
* https://www.acmicpc.net/problem/3046
* BOJ 백준온라인져지 3046 R2 풀이
*/
int main () {
float R1, S;
scanf("%f%f", &R1, &S);
printf("%d", (int)((R1/2-S)*-2));
}
view raw BOJ_3046.cpp hosted with ❤ by GitHub


저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 1076 저항 풀이  (0) 2018.02.17
BOJ 백준온라인져지 2010 플러그 풀이  (0) 2018.02.17
BOJ 백준온라인져지 4963 섬의 개수 풀이  (0) 2018.02.13
BOJ 백준온라인져지 11004 K번째 수 풀이  (0) 2018.02.10
BOJ 백준온라인져지 1219 오민식의 고민 풀이  (0) 2018.02.08

1. 모든 섬을 DFS 해본다.

2. 이미 방문했다면 DFS 를 중단한다.

3. w 너비, h 높이 가 순서대로 입력되므로 잘 체크하자

4. 입력을 반대로 받고 처리하면 된다.

#include <cstdio>
#include <vector>
/**
* https://www.acmicpc.net/problem/4963
* BOJ 백준온라인져지 4963 섬의 개수 풀이
*/
using namespace std;
int xxxx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int yyyy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
int N, M;
vector<vector<bool> > visited;
vector<vector<int> > map;
void dfs (int x, int y) {
if (visited[x][y]) return;
visited[x][y] = true;
for (int i = 0; i < 8; i++) {
int cx = x + xxxx[i]; int cy = y + yyyy[i];
if (cx < 0 || cy < 0 || cx >= N || cy >= M || map[cx][cy] == 0) continue;
dfs(cx, cy);
}
}
int main () {
while (1) {
scanf("%d%d", &M, &N);
if ((N | M) == 0) break;
map = vector<vector<int> >(N, vector<int>(M, 0));
visited = vector<vector<bool> >(N, vector<bool>(M, false));
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
scanf("%d", &map[i][j]);
}
}
int result = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] && !visited[i][j]) {
result++;
dfs(i, j);
}
}
}
printf("%d\n", result);
}
}
view raw BOJ_4963.cpp hosted with ❤ by GitHub

더 좋은 방법

1. visited 를 사용하지 않고, map 을 0 으로 만든다.

2. 0 으로 만들면 다시 배열을 초기화해줄 필요도 없다.

저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 2010 플러그 풀이  (0) 2018.02.17
BOJ 백준온라인져지 3046 R2 풀이  (0) 2018.02.15
BOJ 백준온라인져지 11004 K번째 수 풀이  (0) 2018.02.10
BOJ 백준온라인져지 1219 오민식의 고민 풀이  (0) 2018.02.08
BOJ 백준온라인져지 1865 웜홀 풀이  (0) 2018.02.06

quick select 라는게 있어서 공부하고 사용했다.


1. quick select 함수 실행

2. pivot = partition

3. partition 에서는 pivot 을 기준으로 작은값과 큰 값을 나눈다.

4. pivot 을 정하면 그 것은 고정이 된다.

5. pivot 을 확인해서 값 출력

#include <cstdio>
/**
* https://www.acmicpc.net/problem/11004
* BOJ 백준온라인져지 11004 K번째 수 풀이
*/
void swap (int arr[], int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
int partition (int arr[], int l, int r) {
int pivot = arr[l];
int low = l + 1;
int high = r;
while (low <= high) {
while (pivot >= arr[low] && low <= r) low++;
while (pivot <= arr[high] && high >= l + 1) high--;
if (low <= high) swap(arr, low, high);
}
swap(arr, l, high);
return high;
}
int quickSelect (int arr[], int l, int r, int k) {
int pivot = partition(arr, l, r);
if (pivot == k) return arr[k];
else if (pivot < k) return quickSelect(arr, pivot + 1, r, k);
else return quickSelect(arr, l, pivot - 1, k); // if (pivot > k)
}
int main () {
int n, k;
scanf("%d%d", &n, &k);
int arr[n];
for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
printf("%d", quickSelect(arr, 0, n - 1, k - 1));
}
view raw BOJ_11004.cpp hosted with ❤ by GitHub


저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 3046 R2 풀이  (0) 2018.02.15
BOJ 백준온라인져지 4963 섬의 개수 풀이  (0) 2018.02.13
BOJ 백준온라인져지 1219 오민식의 고민 풀이  (0) 2018.02.08
BOJ 백준온라인져지 1865 웜홀 풀이  (0) 2018.02.06
BOJ 백준온라인져지 1613 역사 풀이  (0) 2018.02.03

1. 한 바퀴 돌린다.

2. 한 바퀴 더 돌리면서는 업데이트 될 때마다, 무한대로 설정한다.

3. 그걸로 출력

#include <cstdio>
#include <vector>
/**
* https://www.acmicpc.net/problem/1219
* BOJ 백준온라인져지 1219 오민식의 고민 풀이
*/
struct Edge {
int s, e, pr;
};
using namespace std;
long long INF = 2147483647L * 214214214;
int main () {
int N, startCity, endCity, M;
scanf("%d%d%d%d", &N, &startCity, &endCity, &M);
long long *d = new long long[N];
long long *p = new long long[N];
for (int i = 0; i < N; i++) {
d[i] = -INF;
}
Edge edge;
vector<Edge> edges;
for (int i = 0; i < M; i++) {
int S, E, P;
scanf("%d%d%d", &S, &E, &P);
edge.s = S; edge.e = E; edge.pr = -P;
edges.push_back(edge);
}
for (int i = 0; i < N; i++) {
scanf("%lld", &p[i]);
}
d[startCity] = p[startCity];
bool gee = false;
for (int k = 0; k < 2; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
int s = edges[j].s; int e = edges[j].e; int pr = edges[j].pr;
if (d[s] == -INF) continue;
else if (d[s] == INF) d[e] = INF;
else if (d[e] < d[s] + p[e] + pr) {
d[e] = d[s] + p[e] + pr;
if (k) d[e] = INF;
}
}
}
}
if (d[endCity] == -INF) printf("gg");
else if (d[endCity] == INF) printf("Gee");
else printf("%lld", d[endCity]);
}
view raw BOJ_1219.cpp hosted with ❤ by GitHub


저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 4963 섬의 개수 풀이  (0) 2018.02.13
BOJ 백준온라인져지 11004 K번째 수 풀이  (0) 2018.02.10
BOJ 백준온라인져지 1865 웜홀 풀이  (0) 2018.02.06
BOJ 백준온라인져지 1613 역사 풀이  (0) 2018.02.03
BOJ 백준온라인져지 10159 저울 풀이  (0) 2018.02.01

다익스트라 알고리즘과 차이점

1. 음수 가중치가 있어도 작동이 된다.

2. 음수 사이클을 체크할 수 있다.


내가 작성한 코드의 worst time complexity 예상 O(V^2*E)

작동방식

1. distance 를 모두 임의의 값으로 체운다.

2. edge 에 가중치들을 넣는다.

3. vertex 만큼 forloop 을 하나 돌린다.

4. 그 안에서 연결된 edge 를 다 체크해준다.

5. cnt 가 N 이 된다는 것은 update 가 된다는 뜻 ( 음수 사이클 )

#include <cstdio>
#include <vector>
/**
* https://www.acmicpc.net/problem/1865
* BOJ 백준온라인져지 1865 웜홀 풀이
*/
using namespace std;
int N, M;
int main () {
int T;
scanf("%d", &T);
while(T--) {
int N, M, W;
scanf("%d%d%d", &N, &M, &W);
int *d = new int[501];
vector<vector<pair<int, int> > > edges(N + 1);
for (int i = 0; i < 501; i++) {
d[i] = 987654321;
}
d[1] = 0;
for (int i = 0; i < M; i++) {
int S, E, T;
scanf("%d%d%d", &S, &E, &T);
edges[S].push_back(make_pair(E, T));
edges[E].push_back(make_pair(S, T));
}
for (int i = 0; i < W; i++) {
int S, E, T;
scanf("%d%d%d", &S, &E, &T);
edges[S].push_back(make_pair(E, -T));
}
bool update = true;
int cnt = 0;
while (update && cnt != N) {
cnt++;
update = false;
for (int i = 1; i <= N; i++) {
for (int j = 0; j < edges[i].size(); j++) {
if (d[edges[i][j].first] > d[i] + edges[i][j].second) {
d[edges[i][j].first] = d[i] + edges[i][j].second;
update = true;
}
}
}
}
printf("%s\n", cnt == N ? "YES" : "NO");
}
}
view raw BOJ_1865.cpp hosted with ❤ by GitHub


저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 11004 K번째 수 풀이  (0) 2018.02.10
BOJ 백준온라인져지 1219 오민식의 고민 풀이  (0) 2018.02.08
BOJ 백준온라인져지 1613 역사 풀이  (0) 2018.02.03
BOJ 백준온라인져지 10159 저울 풀이  (0) 2018.02.01
BOJ 백준온라인져지 1389 케빈 베이컨의 6단계 법칙 풀이  (0) 2018.01.30

1. 입력값이 1 2 면 [1][2] = -1 [2][1] = 1

2. Floyd-Warshall 실행

3. 그대로 출력


#include <cstdio>
/**
* https://www.acmicpc.net/problem/1613
* BOJ 백준온라인져지 1613 역사 풀이
*/
using namespace std;
int N, M;
void floyd (int edges[][401]) {
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (edges[i][k] == 1 && edges[k][j] == 1) edges[i][j] = 1, edges[j][i] = -1;
}
}
}
}
int main () {
scanf("%d%d", &N, &M);
int (*edges)[401] = new int[401][401];
for (int i = 0; i < M; i++) {
int x, y;
scanf("%d%d", &x, &y);
edges[x][y] = -1;
edges[y][x] = 1;
}
floyd(edges);
scanf("%d", &M);
for (int i = 0; i < M; i++) {
int x, y;
scanf("%d%d", &x, &y);
printf("%d\n", edges[x][y]);
}
}
view raw BOJ_1613.cpp hosted with ❤ by GitHub
저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 1219 오민식의 고민 풀이  (0) 2018.02.08
BOJ 백준온라인져지 1865 웜홀 풀이  (0) 2018.02.06
BOJ 백준온라인져지 10159 저울 풀이  (0) 2018.02.01
BOJ 백준온라인져지 1389 케빈 베이컨의 6단계 법칙 풀이  (0) 2018.01.30
BOJ 백준온라인져지 11376 열혈강호 2 풀이  (0) 2018.01.27

아이디어만 있다면 간단한 문제


기존 floyd-warshall 알고리즘과 동일하게

1. i > j 를 갱신하고 싶다.

2. 어떻게 하지?

3. i > k > j 가 되는경우

끝.

#include <cstdio>
/**
* https://www.acmicpc.net/problem/10159
* BOJ 백준온라인져지 10159 저울 풀이
*/
using namespace std;
int N, M;
void floyd (int edges[][101]) {
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (edges[i][k] && edges[k][j]) edges[i][j] = 1;
}
}
}
}
int main () {
scanf("%d%d", &N, &M);
int (*edges)[101] = new int[101][101];
for (int i = 0; i < M; i++) {
int x, y;
scanf("%d%d", &x, &y);
edges[x][y] = 1;
}
floyd(edges);
for (int i = 1; i <= N; i++) {
int result = 0;
for (int j = 1; j <= N; j++) {
if (edges[i][j] == 0 && edges[j][i] == 0) result++;
}
printf("%d\n", result - 1);
}
}
view raw BOJ_10159.cpp hosted with ❤ by GitHub
저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 1865 웜홀 풀이  (0) 2018.02.06
BOJ 백준온라인져지 1613 역사 풀이  (0) 2018.02.03
BOJ 백준온라인져지 1389 케빈 베이컨의 6단계 법칙 풀이  (0) 2018.01.30
BOJ 백준온라인져지 11376 열혈강호 2 풀이  (0) 2018.01.27
BOJ 백준온라인져지 2822 점수 계산 풀이  (0) 2018.01.25

i -> j 를 갈 때,

i -> k -> j 를 가는게 더 짧으면 업데이트 한다.


floyd-warshall 의 아이디어다.


O(V^3)


다음 문제때, 조금 더 자세히 살펴보면서 증명까지 가능하면 해보겠다.

#include <cstdio>
#include <vector>
/**
* https://www.acmicpc.net/problem/1389
* BOJ 백준온라인져지 1389 케빈 베이컨의 6단계 법칙 풀이
*/
using namespace std;
vector<vector<int> > d;
int N, M;
void floyd () {
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
}
}
}
}
int main () {
scanf("%d%d", &N, &M);
d.resize(N + 1);
for (int i = 1; i <= N; i++) {
d[i].resize(N + 1);
for (int j = 1; j <= N; j++) {
d[i][j] = 1912412;
}
d[i][i] = 0;
}
for (int i = 0; i < M; i++) {
int a, b;
scanf("%d%d", &a ,&b);
d[b][a] = d[a][b] = 1;
}
floyd();
int result = 135812375;
int idx = 0;
for (int i = 1; i <= N; i++) {
int temp = 0;
for (int j = 1; j <= N; j++) {
if (d[i][j] == 1912412) continue;
temp += d[i][j];
}
if (result > temp) result = temp, idx = i;
}
printf("%d", idx);
}
view raw BOJ_1389.cpp hosted with ❤ by GitHub


저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 1613 역사 풀이  (0) 2018.02.03
BOJ 백준온라인져지 10159 저울 풀이  (0) 2018.02.01
BOJ 백준온라인져지 11376 열혈강호 2 풀이  (0) 2018.01.27
BOJ 백준온라인져지 2822 점수 계산 풀이  (0) 2018.01.25
BOJ 백준온라인져지 11375 열혈강호 풀이  (0) 2018.01.23

이분 매칭을 2번 작동하면 된다.


글을 작성하다 날려서 더 길게 적고싶지 않다.

#include <cstdio>
#include <vector>
/**
* https://www.acmicpc.net/problem/11376
* BOJ 백준온라인져지 11376 열혈강호 2 풀이
*/
using namespace std;
vector<vector<int> > adj;
vector<int> match;
vector<bool> visited;
int workCount;
bool dfs (int here) {
if (visited[here]) return false;
visited[here] = true;
for (int there = 1; there <= workCount; there++) {
if (adj[here][there]) {
if (match[there] == -1 || dfs(match[there])) {
match[there] = here;
return true;
}
}
}
return false;
}
int main () {
int personCount;
scanf("%d%d", &personCount, &workCount);
adj.resize(personCount + 1);
for (int i = 1; i <= personCount; i++) {
adj[i].resize(workCount + 1);
int length;
scanf("%d", &length);
for (int j = 0; j < length; j++) {
int work;
scanf("%d", &work);
adj[i][work] = 1;
}
}
int result = 0;
match = vector<int>(workCount + 1, -1);
for (int i = 1; i <= personCount; i++) {
for (int j = 0; j < 2; j++) {
visited = vector<bool>(personCount + 1, false);
if (dfs(i)) result++;
}
}
printf("%d", result);
}
view raw BOJ_11376.cpp hosted with ❤ by GitHub
저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 10159 저울 풀이  (0) 2018.02.01
BOJ 백준온라인져지 1389 케빈 베이컨의 6단계 법칙 풀이  (0) 2018.01.30
BOJ 백준온라인져지 2822 점수 계산 풀이  (0) 2018.01.25
BOJ 백준온라인져지 11375 열혈강호 풀이  (0) 2018.01.23
BOJ 백준온라인져지 14502 연구소 풀이  (0) 2018.01.14

+ Recent posts

티스토리툴바