2406 안정적인 네트워크 G3
#mst
지문에 낚시가 많지만 1번 정점은 아~~~무 쓸데가 없다.
adjust matrix를 구성할때도, 1번해당되는 edge는 연결안해도 된다.
이후 mst를 무난하게 구성하고, 필요한 weight, edge정보, 갯수를 다 추출하면 된다.
1557 제곱 ㄴㄴ D5
#math
우선 https://gratus-blog.tistory.com/74 이걸 많이 참고해서 공부하여 구현하였다.
뫼비우스 함수를 정의해야하는데,
μ(1)=1
이 제곱수로 나누어지면 μ(n)=0
이 서로 다른 k개의 소인수의 곱이면 μ(n)=(−1) ^ k으로 정의 할 수 있다.
이후 포함배제 원리에 따라 1부터 N까지 제곱인수가 없는 수를 계산하고, 이분 탐색을 통해 k번째수를 찾아보자.
8464 Non-Squarefree Numbers D5
#math
앞서 설명한 #1557번에 n의 범위가 다르고 반대로 K번째 제곱수를 찾는 문제이다.
이분탐색하는 코드에서 전체 갯수가 아닌 N-전체 갯수하면 되는 덤으로 따라오는 문제
(이걸 오랫동안 생각했다)
4991 로봇청소기 G1
#bfs #tsp
내가 푼 방법은 현재 위치를 1번, 나머지 청소해야할 부분을 2,3,4.. 노드라고 생각하고 각 node별로 갈 수 있는 distance를 인접행렬로 만든 다음, 외판원 순회를 해주었다.
이거보다 더 쉽게 푸는 방법이 있는 듯하다. 구현 + tsp 무조건 플레이상이라고 생각하는데 G1인거봐선..
8336 Chess G1
#ad_hoc, #math
배치는 순열의 사이클 구조를 이용하여 n이 4의 배수이거나 n ≡ 1 mod 4일 때만 가능하며, 그 외의 경우는 불가능하다.
조건을 만족할땐, 팩토리얼 연산을 통해 배치 수를 구해보자.
28449 누가 이길까 G5
#binary_search, #sorting #hash
나이브하게 풀면 n^2이 난다. n <= 100000이기 때문에 시간초과 남.
target배열을 정렬한 다음, binary search를 통하여 몇번쨰 인덱스에 넣을수 있는지 찾아보자.
결과 인덱스보다 앞에있으면 이길수있는 상대, 뒤에있으면 지는 상대일것이다.
추가로 비기는 경우를 대비해 미리 hash map에다 count해 비기는 상대는 미리 구할 수 있을 것이다.
1068 트리 G5
#dfs #tree
트리를 구성하고 제거할 정점을 graph를 돌면서 제거해주자.
제거하는데 있어 인덱스 문제가 생길수 있으니 그래프를 deepcopy하여 처리하자.
이후 dfs해서 leaf node들을 체크해 1씩 증가시켜주자.
만약 제거할 node가 정점이라면 답은 0으로 따로 예외처리를 해주자.
3987 보이저 1호 G5
#implement #graph
그냥 머... 지문에 있는 대로 구현해주면 된다.
맵 넘어가면 그만 탐색하고500x500이라 1000000번 순회하면 무한 루프라고 판단되어 그만하게 처리해주었다.
개인적으로 같은 난이도였던 #2344보다 훨씬 쉬웠음.
그 문제는 배열의 인덱스를 수식으로 관리해주었어야 했는데 이건 그런것도 없다.
28448 광기의 PS P5
#greedy
관찰을 해보면, 5 * K >= K * T 라면, 그 문제를 푼다해도 무조건 광기력이 0이 된다. 다음과 같은 case들은 우선적으로 바로 풀어주자.
나머지 case들에 대해선, 문제의 난이도에 대해 정렬을 해주고, 따로 tuple에 최소 n만큼 되어야 그 문제를 풀이 할 수 있는 시간을 정의해 주었다.
이후엔 구현
2660 회장뽑기 G5
#bfs
각 node를 시작으로 하는 BFS를 수행해주고 가장 긴 distance를 구하는 문제이다.
머.. 무난무난해서 설명할게 없다.
17839 Baba is Rabbit G5
#bfs
간단한 BFS 문제지만, 정점번호가 string으로 되어 있는 문제이다.
dictonary에서 정점번호 - string을 매칭시켜준 다음, bfs하면된다.
체크해야하는 점은 매번 value를 찾는 과정을 O(n)으로 수행하면, TLE가 발생하기 때문에, 역방항 dictionary를 만들어서 O(1)로 해결해주어야 한다.
12634 Stock Charts (Large) P2
#bipartite_matching
주식차트를 이분그래프로 변경하기 위해서 (i, k)번째 시점이 (j, k) 시점 보다 값이 적다면, 이분그래프를 그릴 수 있다.
그뒤론 적절하게 이분매칭의 최대 수는 같이 그릴 수 있는 차트와 같기 때문에 n - 이분매칭 최대수가 답이 된다.
여담으로 똑같은 코드로 12633, 12988을 해결할 수 있다.
'ps > Solved' 카테고리의 다른 글
| 9월 3째주 PS 정리 (0) | 2024.09.16 |
|---|