2045. Second Minimum Time to Reach Destination
신호등이 있는 그래프가 주어질 때 1부터 n으로 가는 경로 중에서 두번째로 짧은 경로를 구하는 문제. 일단 신호등이 change 마다 바뀌는데 다시 보면 시간이 change의 짝수 배이면 초록불, change의 홀수 배이면 빨간불이다. 이제 두번째로 짧은 경로를 구해야 하는데 마지막 도시에 두번째로 도착한 시간이 두번째로 짧은 경로가 된다. (가까운 순으로…
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
hard 68
269 268 218. The Skyline Problem
빌딩이 주어질 때 스카이라인을 출력하는 문제. 상당히 빡센 문제이다. heap (pq)를 쓴다는 것을 알고 봐도 쉽지 않음. 일단 왼쪽부터 오른쪽으로 하나씩 스캔하는 방식으로 진행하면서 현재까지 겹쳐있는 빌딩의 높이를 관리해주면 풀 수 있다. 스캔은 빌딩 시작과 끝을 기준으로 해야 하므로 주어진 빌딩 배열을 분해해주자. 그리고 현재까지 빌딩 높이 관리는 가…
267 2551. Put Marbles in Bags
가방 안의 돌들을 k 그룹으로 묶을 때 최소 합과 최대 합의 차이를 구하는 문제. 처음에는 DP 느낌이지만 수가 너무 많다. 정답은 그리디로 가면 된다. 뭔가 정렬 느낌이긴 했는데 잘 안돼서 에디토리얼 참고함. 사진은 에디토리얼에서 가져옴 일단 시작 돌과 마지막 돌은 무조건 포함해야 하니 제외하자. 그러면 k-1번 가방의 돌들을 나누는 문제가 된다. 여기서…
266 514. Freedom Trail
ring와 입력해야 할 key가 주어질 때 최소 횟수로 ring을 돌려서 key를 만드는 횟수를 구하는 문제 간단한 DP로 풀 수 있다. 현재 위치 기준으로 왼쪽, 오른쪽으로 돌려가며 찾을 수 있다. 시간 복잡도는 O(R^2 K) left, right로 돌릴 때의 문자열을 찾을 때 전처리를 통해 미리 구해놓으면 더 빨리 구할 수 있다. 또는, 에디토리얼 보…
265 1289. Minimum Falling Path Sum II
행끼리 인접하지 않은 열의 수를 더해서 최소가 되도록 맨 아래까지 가는 합을 구하는 문제. O(n^3) 풀이는 매우 쉬운 DP. O(n^2) 풀이를 생각해보자. 그리디하게 생각해보면 된다. 다음 row로 넘어갈 때 col이 같지만 않으면 된다. 즉, col이 어떤 곳이라도 찍을 수 있다는 것. 이를 잘 이용하면 전체 스캔할 필요 없이 최솟값인 곳과 두번째 …
254 2402. Meeting Rooms III
미팅룸이 n개 있고 미팅 시간이 주어졌을 때 가장 미팅이 많이 한 룸을 구하는 문제. 미팅이 가능한 방이 여러개 있을 경우 가장 작은 번호의 방이 선택되며 현재 가능한 방이 없다면 가장 빠른 방을 사용한다. 그리디 방식으로 가능하다. 일종의 스케줄링 + 구현 문제라고 봐도 될 듯. 문제에 나온 그대로 작은 방부터 탐색하면서 미팅이 가능하면 미팅을 하면 된다…
247 1463. Cherry Pickup II
로봇이 첫 번째 행의 첫 번째 열과 마지막 열에 2개 있고 아래로 3 방향으로 내려가면서 최대로 체리를 얻을 수 있는 개수를 구하는 문제. 일단 간단한 DP 문제이긴 한데 궁금증이 하나 있다. 두 로봇이 같은 셀로 들어가는게 좋은 경우가 있을까? 결론은 없다. 만약 두 로봇이 같은 셀로 들어갔다고 해도 다음 경로를 정할 때는 다른 셀로 들어가야 할텐데 굳이…
237 2360. Longest Cycle in a Graph
그래프가 주어질 때 가장 길이가 긴 사이클의 길이를 구하는 문제. 문제 자체는 쉽다. 사이클 중에 가장 긴 길이를 구하면 되는데 직접 구현은 살짝 복잡하긴 하다. 먼저 노드에서 나가는 엣지는 최대 1개이므로 그냥 바로 다음 노드로 건너가면 된다. 다음 노드로 갈 때 level 변수에 1씩 증가하다가 이미 방문한 노드가 있다면 현재 노드와 방문했던 노드의 l…
236 2321. Maximum Score Of Spliced Array
배열 2개가 주어지고, 배열의 일부 구간을 다른 배열과 swap 가능할 때 두 배열의 합 중 최대가 가장 큰 값을 구하는 문제. 딱 보니 DP라서 처음에는 top-down으로 풀었다. 해당 최댓값은 배열 하나에만 계산되므로 배열 2개를 서로 바꿔서 한번 더 돌려주면 된다. 정답이 나오긴 하는데 2792 ms로 하위 5%의 성능.. 결국 bottom-up 으…
235 2172. Maximum AND Sum of Array
슬롯이 있고 숫자를 한 슬롯에 최대 2개까지 집어넣을 수 있다. 이때 슬롯의 번호와 숫자를 AND 연산한 합 중에 최대를 구하는 문제. 비트마스크 DP 이다. 처음에는 슬롯에 2개씩 들어가므로 슬롯의 크기를 2배로 해서 돌려봤는데 시간 초과... 결국 비트마스크를 2개 써서 통과. dp[i][slot1][slot2] = slot1, slot2에 숫자가 있을…