반응형
https://www.acmicpc.net/problem/2617
2617번: 구슬 찾기
모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서
www.acmicpc.net
[ 문제풀이 ]
이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.
https://rudalsd.tistory.com/24
[ 알고리즘 ] 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)
오늘 설명할 알고리즘은 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)입니다. 이 알고리즘은 dijkstra와 비슷하게 각 정점까지 가는 최단 거리를 알아낼 수 있습니다. 플로이드 와샬 알고리즘이 dijk
rudalsd.tistory.com
1. arr[ n ][ n ] 배열을 만들어서 각 구슬의 관계를 저장합니다.
2. 플로이드 와샬 알고리즘을 이용하여 나머지 구슬들의 관계를 갱신해 줍니다.
3. 2중 for문을 통해 각각의 구슬이 가볍거나 무거운 구슬이 (N + 1) / 2 개보다 많거나 같으면 ans++를 해줍니다.
4. ans를 출력합니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | #include<iostream> using namespace std; int N, M; int arr[100][100]; int main() { scanf("%d %d", &N, &M); for (int i = 0; i < M; i++) { int a, b; scanf("%d %d", &a, &b); arr[a][b] = 1; arr[b][a] = -1; } for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { for (int k = 1; k <= N; k++) { if (arr[j][i] == arr[i][k] && arr[j][i] != 0) { arr[j][k] = arr[j][i]; } } } } int ans = 0; for (int i = 1; i <= N; i++) { int cnt[2] = { 0 }; for (int j = 1; j <= N; j++) { if (arr[i][j] == 1) { cnt[0]++; } else if (arr[i][j] == -1) { cnt[1]++; } } if (cnt[0] >= (N + 1) / 2 || cnt[1] >= (N + 1) / 2) { ans++; } } printf("%d", ans); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 3066번 - 브리징 시그널 (C++) (0) | 2023.03.01 |
|---|---|
| [ 백준 ] 2660번 - 회장뽑기 (C++) (0) | 2023.02.28 |
| [ 백준 ] 18235번 - 지금 만나러 갑니다 (C++) (0) | 2023.02.26 |
| [ 백준 ] 18405번 - 경쟁적 전염 (C++) (0) | 2023.02.25 |
| [ 백준 ] 1613번 - 역사 (C++) (0) | 2023.02.24 |