15488 나이트가 체스판을 벗어나지 않을 확률 G5
#dp
bfs나 dfs로 관리해준다면 visited의 존재가 없기 때문에 8^50번의 탐색이 필요하다. 따라서 dp를 이용해 중복연산을 제거해보자.
dp[i][j] = 현재 i,j에 말이 있을 확률이라고 가정해보자.
그렇다면, 처음 위치 dp[x][y]는 1이 될 것이다. 매 이동횟수 k를 진행하면서 갈 수 있는 경우의수는 8가지 이기 때문에
dp[next_knight_move][] += dp[x][y] * 0.125될 것이다. 이 과정을 위치에 벗어나지 않는한 계속 해주자.
dp보단 브루트포스에 가깝다... 시간복잡도 O(n^4)
1161 버스 P3
#greedy
탑승 정거장 기준으로 정렬을 해보자.
25585 86 ─에이티식스─ 1 G5
#tsp #graph
대각선으로 BFS을 하여 adjust matrix를 만들 수 있다.
그런 다음, 접근을 못하는 정점이 있으면 불가능한 걸 알 수 있다.
그 다음 tsp를 활용 해 최단 거리를 구할 수 있다.
난이도에 비해 어렵게 풀었는데 n의 범위가 작아서 10!으로 permutation을 만들면 brute force으로도 풀리는 듯 하다.
20757 Roadside optimization G5
#dsu
평범한 dsu 문제
adjust matrix를 순회하면서 i,j가 1인 경우, parent를 find 했을 때, parent가 다르다면 union을 해준 다음, +=1 해주면 된다.
그것이 최소의 간선으로 전체를 순회할 수 있는 방법 중 하나이다.
20551 Sort 마스터 배지훈의 후계자 S4
#sort, #hash
정렬한 다음, dictonary와 같은 hash set으로 처음 등장한 index를 관리해주면 된다.
풀고 난 다음 태그를 봤는데 이분탐색이 있어 이방법도 있겠구나 싶었다.
http://boj.kr/da8cf1e839bf4e7f9a53ebaa884725df
2141 우체국 G4
#greedy #prefix_sum
관찰 해보았을 때, 우체국은 사람이 있는 장소에 설치하는게 가장 최적일 것이다.
그리고 Greedy하게 푸는 방법을 생각해보았을 때 현재 index기준 사람이 전체 사람의 50%가 넘어가는 시점에 설치해야 한다. (이 과정이 증명하기 힘들지만, 가장 최적의 방법이다.) 이 과정을 누적합을 이용해서 구현해주자.
추가로 input으로 들어오는 우체국의 위치가 정렬이 되어 있지 않은듯하다. sort를 해주어야 함.
이 방법외에도 여러가지 풀이방법이 존재하는 듯하다.
23850 Cijanobakterije G2
#graph
트리의 지름을 구하는 문제와 유사하다.
다만, 모든 정점이 하나의 트리로 구성되어 있지 않기 때문에 bfs로 탐색 할 수 있는 트리들의 지름의 합을 구해주어야 한다.
트리의 지름을 구하는 방법은 임의의 정점 w를 잡고 가장 길이가 먼 x를 잡은 다음, x에서 가장 먼 정점 y를 잡는다면, x->w->y는 트리의 지름이 된다.
28251 나도리합 G3
#dsu
union을 했을 때, 그 그룹 내에 모든 power의 곱의 합을 쿼리로 출력하는 문제
union할 때 power라는 새로운 리스트를 만들어 parent를 관리함과 동시에 power을 update해주자.
쿼리가 들어오면 매 쿼리마다 그 그룹을 union하고, power을 출력해주면 되는 문제.
20153 영웅이는 2의 거듭제곱을 좋아해! 영웅이는 2의 거듭제곱을 좋아해! S2
#math
2^n개가 홀수개 있다는 거는, 해당 비트위치의 연산을 xor 했을때 1인 경우를 의미할 것이다.
그리고 최대 1개를 지운 다는 것은 전체 xor 한 값에 한번 더 해당 값을 xor연산 한것과 동치 일 것이다.
그렇게 해준 다음, 위 2 case의 최댓값을 출력시켜주자.
'ps > Solved' 카테고리의 다른 글
| 11월 1째주 PS정리 (0) | 2024.10.28 |
|---|---|
| 10월 4째주 PS정리 (0) | 2024.10.22 |
| 10월 2째주 PS 정리 (0) | 2024.10.07 |
| 10월 1째주 PS 정리 (0) | 2024.09.30 |
| 9월 4째주 PS정리 (2) | 2024.09.24 |