A - CAPS LOCK
입력 받아서 대문자로 변환하는 문제입니다.
B - Yellow and Red Card
옐로 카드를 2장 받거나, 레드 카드를 1장 받으면 퇴장을 당합니다. 그 후에 퇴장 당한 플레이어를 찾는 문제입니다.
옐로는 +1, 레드는 +2를 해서 2점 이상이면 Yes를 출력하였습니다.
C - Four Variables
AB+CD=N을 만족하는 (A,B,C,D) 를 찾는 문제입니다.
먼저 O(N^2) 풀이를 제출하였는데 N이 10^5 이기 때문에 TLE를 받았습니다.
| 1 (1, 1) 2 (1, 2) (2, 1) 3 (1, 3) (3, 1) 4 (1, 4) (2, 2) (4, 1) 5 (1, 5) (5, 1) 6 (1, 6) (2, 3) (3, 2) (6, 1) 7 (1, 7) (7, 1) 8 (1, 8) (2, 4) (4, 2) (8, 1) 9 (1, 9) (3, 3) (9, 1) |
작은 N에 대해서 경우의 수를 전부 적어 보았더니 A와 B를 곱해서 AB를 만들 수 있는 경우의 수는 AB의 약수의 개수와 같았습니다. 약수를 구하는 함수를 만들어서 다시 제출하였는데 TLE를 받았고, 배수를 이용하여 약수의 개수를 구했더니 AC를 받았습니다.
D - Unicyclic Component
각각의 연결 요소에 대하여, 정점의 개수와 간선의 개수가 같다면 Yes, 그렇지 않다면 No를 출력하는 문제입니다.
dfs로 정점의 개수와 간선의 개수를 세는 코드를 제출했는데 계속 TLE를 받아서 시간 안에 풀지 못 하였습니다. 에디토리얼을 참고해 봤더니 Disjoint set이라는 자료 구조를 사용하는 문제였습니다. Disjoint set을 공부한 뒤에 백준에서 기본 문제인 1717 집합의 표현, 1976 여행 가자, 1043 거짓말 등의 문제를 푼 뒤에 다시 풀었더니 해결할 수 있었습니다.
union으로 연결 요소를 찾은 후에, 딕셔너리를 이용해서 정점의 개수와 간선의 개수를 세었더니 AC를 받았습니다.