[백준]10159 저울(c++)
백준 10159 저울
1. 문제
2. 접근법
- 문제 접근
- 각 물건에 대해서 그 물건과 비교 결과를 알 수 없는 물건의 개수를 출력해야 하므로 2차원 배열을 이용한다. 즉 플로이드 와샬 알고리즘을 사용하는 문제이다.
- 앞의 물건이 뒤의 물건보다 더 무거우므로 물건을 입력받을 때,
a보다 b가 무거우면 1, 그 반대인 경우에는 -1로 셋팅해준다.
- 노드를 추가로 생성하여 삼중 for문을 돌리면서 거쳐가는 노드에 해당하는 값이 찾고자하는 물건의 무게와 같은 경우, 그리고 0이 아닌 경우에 해당 값을 업데이트 해준다.
- 출력을 위해 이중 for문을 돌리면서 ans값에는 본인을 제외한 값을 초기값으로 셋팅해주고 0이 아닌 경우에 ans를 줄인 후, 마지막으로 ans를 출력시킨다.
3. 코드
#include <algorithm>
#include <iostream>
using namespace std;
int map[101][101];
//floyd-warshall 알고리즘
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, M, a, b, ans;
cin >> N;
cin >> M;
for (int i = 0; i < M; i++)
{
cin >> a >> b;
map[a][b] = 1;
map[b][a] = -1;
}
for (int k = 1; k <= N; k++)
{
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
if (map[i][k] == map[k][j] && map[i][k] != 0)
map[i][j] = map[i][k];
}
}
}
for (int i = 1; i <= N; i++)
{
ans = N - 1;
for (int j = 1; j <= N; j++)
{
if (map[i][j] != 0)
ans--;
}
cout << ans << "\n";
}
return 0;
}
4. 시간복잡도
플로이드 와샬 알고리즘은 기본적으로 삼중 for문을 돌리므로 O(N^3)의 시간복잡도를 가진다.
여기서는 시간제한이 1초인데 N값이 최대 100이므로 1000000, 즉 100만이 되어 1억을 넘지 않는다.
따라서 1초이내로 구현이 가능하다.
5. 결과
Author And Source
이 문제에 관하여([백준]10159 저울(c++)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kgm4620/백준10159-저울저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)