서론
그냥 심심해서 몇 문제 풀었는데 좀 괜찮은 문제 얻어간거 같아서 괜찮은 하루였던 듯.
1. BOJ1043 거짓말
만약 두 파티에 공통된 인원이 있다면, 그 두 파티에서 거짓말을 할 수 있는지는 서로 동일하다. 따라서 두 파티 중 하나에라도 속하는 인원들은 두 파티짜리의 한 덩어리(=독립집합) 인원으로 볼 수 있고, 이 점에서 Union-Find를 쓰면 각각의 독립집합을 형성할 수 있다. 약간의 Union-Find 기술을 쓸 수 있는데, 각 독립집합이 하나의 음 아닌 정수로 표현할 수 있는 특정을 갖는다면 -1배하여 독립집합의 루트의 부모에 저장하면 편리하다는 것이다. 여기서는 그 값을 “이 독립집합에 진실을 아는 사람이 있는가”로 정의하여 참일 때 -1, 거짓일 때 0의 값을 넣어준다면 금방 풀 수 있다.
2. BOJ9935 문자열 폭발
예전에 틀렸던 문제 리벤지한건데, 지금 와서 보면 왜 틀렸나 싶을 정도로 캐쥬얼한 문제이다. 그냥 스택(이라지만 모든 원소에 접근 가능한 컨테이너) 만들고 마지막의 suffix가 폭발문자열과 같은지 비교하여 같다면 pop해주면 된다. 굳이 진짜 스택을 사용할 필요는 없고, array로 구현후 tail pointer에 해당하는 변수를 만들어주면 쉽게 구현할 수 있다.
3. BOJ1135 뉴스 전하기
오늘 풀어본 괜찮은 문제 중 하나. 간단하게 트리DP 연습해볼 만한 문제이다. 근데 제한 작아서 naive한 풀이로도 될거같긴 한데 모르겠다. 풀이 중 가장 어려운 아이디어는 전달 이후 모든 서브트리의 정점에 전달되기까지 시간이 오래 걸리는 순으로 먼저 전달해줘야 한다는 걸 그리디를 통해 알아내는 것이다.
4. BOJ11648 지속
단순 구현. 숫자가 매 단계마다 줄어드는데, 이전 단계의 0.9배 이하가 됨을 보장할 수 있기 때문에 로그 시간복잡도가 나온다.
5. BOJ1167 트리의 지름
기초적인 트리지름 구하기 문제. dfs 2번으로 해결 가능.
6. BOJ3997 하이퍼드롬
오늘 풀어본 괜찮은 문제 두번째. 메모리 낭비했다가 MLE 터지긴 했어도 prefix sum의 개념을 다시 한번 되짚을 수 있는 좋은 문제였다.