백준/플로이드 워셜 (3) 썸네일형 리스트형 [USACO] 백준 6156 - Cow Contest https://www.acmicpc.net/problem/6156 힌트 더보기 어떤 소의 순서를 정확히 알기 위해선 자기보다 낮은 스킬의 소와 높은 스킬의 소의 합이 n - 1마리가 되어야 한다. 각 소들의 sparse 한 스킬 관계를 그래프 형태로 정리하는 방법을 생각해본다. 풀이 더보기 소의 순서를 확정하기 위해선 자기보다 높은 스킬의 소가 몇 마리인지, 자기보다 낮은 스킬의 소가 몇 마리인지 알아야 한다. 하지만 입력은 서로 두 소의 상하 관계만이 주어졌을 뿐이다. 파편화된 관계를 가지고 전체 순위를 알 수 있는 방법이 있을까? 사실 순위가 몇위인지 아는 건 딱히 중요하지 않고 순위가 있다는 것을 알아내기만 하면 된다. 각 관계를 높은 스킬의 소가 낮은 스킬의 소로 향하는 단방향 간선을 가진 그래프.. 백준 14588 - Line Friends (Small) www.acmicpc.net/problem/14588 각 선분의 친분 정도를 구해야 하는 문제이다. 친구는 1, 친구의 친구는 2, 친구의 친구의 친구는 3과 같이 친분이 정의되므로 각 선분의 친분 정도는 서로 얼마나 빠르게 다가갈 수 있는지, 즉 각 선분간의 최단 경로를 구해야 하는 것으로 풀이할 수 있다. 우선 이중 for문을 통해 친분의 정도가 1인 선분의 짝을 탐색하여 그 연결을 인접행렬로 구현한다. 그 후 플로이드 워셜을 수행하여 각 선분 사이의 최단 경로를 찾는다. 그 후 질의에 따라 친분의 정도, 혹은 친구가 아닌지를 출력하면 시간 내에 AC를 받을 수 있다. 전체코드 #include #include #include #include using namespace std; int dp[300][.. 백준 1043 - 거짓말 www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 � www.acmicpc.net 지민이가 거짓말을 할 수 있는 파티 개수의 최댓값을 구하는 문제이다. "어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다." 해당 문장에 각별히 유의하여 문제에 접근해보자. 파티에서 거짓말을 할 수 있는지 알 수 있는 여부는 진실을 모르는 사람이 모든 파티에 대해 진실을 아는 사람과 만나지 않아야 함을 알.. 이전 1 다음
