Processing math: 100%
[백준] BOJ 1733 등번호
·
PS/BOJ
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까지의 수만 주어지므로, 각각 앞 번호와 뒷 번..
[백준] BOJ 22354 돌 가져가기
·
PS/BOJ
https://www.acmicpc.net/problem/22354  | Solved.ac 난이도 : P2 |  문제 추천도 : 9/10   🏷️ 그리디  풀이 1. 인접하며 같은 색을 가지는 돌들은 그중 1개 또는 0개만 선택할 수 있습니다.어떤 돌을 선택하려면, 그 돌의 양 옆이 다른 색의 돌이어야하기 때문입니다.2. 1에 의해서 같은 색의 인접한 돌들을 무게가 가장 큰 돌 하나로 치환할 수 있습니다.여기까지 진행하면 돌들의 상태는 WBWBWB...이나 BWBWBW...가 됩니다.3. 또한, 맨 앞과 맨 끝 돌은 선택할 수 없습니다. 4. ⭐ KeyPoint : 다른 색의 돌이 교차하는 상태에서는 n개의 돌 중 색깔에 상관없이 최대 (n2)/2개의 돌을 반드시 선택..
[백준] BOJ 16000 섬
·
PS/BOJ
https://www.acmicpc.net/problem/16000  | Solved.ac 난이도 : P2 | 문제 추천도 : 6/10  🏷️ 그래프 이론, 탐색 단절점을 이용한 풀이도 있다고 한다. 하지만 단순 그래프 탐색 풀이보다 어렵다고 봄.  풀이 1. (상하좌우 네방향으로) 이어져있는 육지들을 각각의 그룹으로 묶어준다. 2. 최외곽에는 항상 바다가 주어지므로 (0,0)에서부터 바다를 탐색한다.육지를 지나갈 수 없는 벽으로 보고 갈 수 있는 바다를 탐색한다.상하좌우+4개의 대각선 방향으로 탐색한다.⭐ KeyPoint -  대각선 방향은 어떤 육지를 거쳐 바깥쪽 바다로 가는 경우이다.아래는 대각선 방향으로 안쪽 바다 -> 육지 -> 바깥쪽 바다로 가는 경우를 설명한다.바다 바다 바..
ddirori가 PS하는 블로그