BOJ

https://www.acmicpc.net/problem/14285  | Solved.ac 난이도 : P5 | 걸린 시간 : 약 20분  🏷️ 최단 경로어떤 알고리즘을 알고 있을 경우 체감 난이도가 확 내려가는 류의 문제를 풀 때마다 문제의 난이도가 절대적일 수가 없다는 생각을 종종 하곤 한다. 이 문제의 경우에도 문제를 읽자마자 '최단 경로 다익 짜면 끝이네' 의 생각이 금방 떠오른다. 발상의 아이디어는 거의 없는데 그래프에서 최단 경로 구하는 게 G1이라 문제 난이도가 P5가 되버리는. 최단 경로 빼면 실제 체감 난이도는 실버급..   풀이 일단 $s$와 $t$가 연결된 상황에서 지울 수 있는 간선의 가중치 합의 최댓값을 생각해보자.이러면 우리는 $s$와 $t$의 최단 경로에 포함되는 간선을 제외한..

https://www.acmicpc.net/problem/1733  | Solved.ac 난이도 : P1 | 문제 추천도 : 8/10 걸린 시간 : 52' 53''  🏷️ 그래프 탐색, DFS이분 매칭 풀이도 존재하며 내 DFS 풀이보다 시간이 더 오래 걸려서 크기가 큰 테스트케이스가 추가된 재채점에서 TLE가 많이 생겨 W.A 처리가 된 코드가 많다. 이분 매칭 등의 더 난해한 풀이 때문에 난이도가 올려치기 되어있는 감이 있다.+) 내 P3 기여로 문제 티어가 P2가 되었다.   풀이 $($관찰$)$ 1. 이런 류의 문제를 많이 풀어봤다면 직관적으로 "아, 이거 그래프로 바꿔서 풀어야겠구나!"를 문제를 읽자마자 알 수 있다. 2. 번호가 1,000,000까지의 수만 주어지므로, 각각 앞 번호와 뒷 번..

https://www.acmicpc.net/problem/22354  | Solved.ac 난이도 : P2 |  문제 추천도 : 9/10   🏷️ 그리디  풀이 1. 인접하며 같은 색을 가지는 돌들은 그중 1개 또는 0개만 선택할 수 있습니다.어떤 돌을 선택하려면, 그 돌의 양 옆이 다른 색의 돌이어야하기 때문입니다.2. 1에 의해서 같은 색의 인접한 돌들을 무게가 가장 큰 돌 하나로 치환할 수 있습니다.여기까지 진행하면 돌들의 상태는 $WBWBWB...$이나 $BWBWBW...$가 됩니다.3. 또한, 맨 앞과 맨 끝 돌은 선택할 수 없습니다. 4. ⭐ KeyPoint : 다른 색의 돌이 교차하는 상태에서는 n개의 돌 중 색깔에 상관없이 최대 $\lceil(n-2)/2\rceil$개의 돌을 반드시 선택..

https://www.acmicpc.net/problem/16000  | Solved.ac 난이도 : P2 | 문제 추천도 : 6/10  🏷️ 그래프 이론, 탐색 단절점을 이용한 풀이도 있다고 한다. 하지만 단순 그래프 탐색 풀이보다 어렵다고 봄.  풀이 1. $($상하좌우 네방향으로$)$ 이어져있는 육지들을 각각의 그룹으로 묶어준다. 2. 최외곽에는 항상 바다가 주어지므로 $($0,0$)$에서부터 바다를 탐색한다.육지를 지나갈 수 없는 벽으로 보고 갈 수 있는 바다를 탐색한다.상하좌우+4개의 대각선 방향으로 탐색한다.⭐ KeyPoint -  대각선 방향은 어떤 육지를 거쳐 바깥쪽 바다로 가는 경우이다.아래는 대각선 방향으로 안쪽 바다 -> 육지 -> 바깥쪽 바다로 가는 경우를 설명한다.바다 바다 바..