MungGu Story

백준 1043번 거짓말 문제링크 ▼ 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 백준 1043번 거짓말 문제 개요 해당문제는 solved.ac 골드 수준의 문제로 분류되고 있습니다. 내용을 보자면, 사람의 수 N과 지민이 이야기의 진실을 하는 사람 리스트, 각 파티에 오는 사람들의 번호가 주어질때, 과장된 이야기를 할 수 있는 파티의 최대 갯수를 반환하는 문제입니다. 지민이의 진실을 알고 있는 사람들에게는 절대 과장된 이야기를 하면 안됩니다. 지민이의 진실을 알지 못하는 사람에게만 과장된 얘기를 하기 위해서는 진실을..

백준 17171번, 집합의표현 문제 알아보기 1717번, 집합의 표현 문제는 disjoint-set, 서로소 집합 관련 문제입니다. 서로소 집합 개념은 MST문제을 풀때 자주 사용하는 크루스컬 알고리즘에서도 활용되는 유용한 개념입니다. 본 문제 난이도는 solved.ac기준, 골드4로 일반 코딩테스트 기준, 중후반대에 나올 수 있는 문제입니다. 시간제한은 2초, 메모리 제한은 128MB입니다. 초기에 {0}, {1}, {2}, .... {N}의 N+1개 집합이 있다고 할때, 이에 대한 합집합 연산, 두 원소가 같은 집합에 포함되어 있는지 확인하는 연산을 출력하는 문제입니다. 이렇게까지만 문제를 보면 단순한 문제로 보일 수도 있지만, N의 입력범위가 최대 백만이란 점에서, disjoined-set 기반의 ..