본문 바로가기
반응형

Problem Solving/프로그래머스14

프로그래머스 광물 캐기 - C++ 풀이 1. dp(dia, iron, stone, idx) = 곡괭이의 각 개수가 (dia, iron, stone)개일 때 minerals[idx...]를 처리하기 위한 최소 피로도 2. 세 가지 곡괭이를 하나씩 사용해보고 최소 피로도를 갖는 경우를 찾는다. 1. dp(dia, iron, stone, idx) = 곡괭이의 각 개수가 (dia, iron, stone)개일 때 minerals[idx...]를 처리하기 위한 최소 피로도 dp(dia, iron, stone, idx)를 위와 같이 정의하자. 각 곡괭이의 개수는 최대 5개이고, 캐야 하는 광물의 개수는 최대 50개로 매우 작기 때문에 O(MN^3)의 시간복잡도도 충분하다. 기저사례는 곡괭이가 하나도 남지 않거나, 남은 광물이 없는 경우이다. 2. 세 가지.. 2023. 9. 5.
프로그래머스 과제 진행하기 - C++ 풀이 1. 시작시간을 기준으로 오름차순 정렬하여 순차적으로 시작한다. 2. 현재 과제를 끝내기 전에 다음 과제를 시작해야 하는 경우, 현재 과제를 중단한다. 중단된 과제들은 스택으로 관리한다. 3. 다음과제를 시작하기 전까지 텀이 존재하는 경우, 텀 동안 중단했던 과제들을 해결한다. 1. 시작시간을 기준으로 오름차순 정렬하여 순차적으로 시작한다. 시작시간에 맞춰 순차적으로 시작해야하므로, 시작시간을 기준으로 오름차순 정렬해둔다. 2. 현재 과제를 끝내기 전에 다음 과제를 시작해야 하는 경우, 현재 과제를 중단한다. 중단된 과제들은 스택으로 관리한다. 만약 현재 과제를 끝내기 전에 다음 과제를 시작해야 하는 경우, 현재 과제를 중단해야 한다. 이때 중단된 과제들은 스택에 넣어둔다. 멈춰둔 과제가 여러 개일 경우.. 2023. 9. 5.
프로그래머스 연속된 부분 수열의 합 - C++ 풀이 1. 투포인터를 사용한다. 부분 수열의 시작과 끝 인덱스를 각각 lo, hi라 하자. 2. sum(lo, hi) k 이면 lo를 늘린다. 1. 투포인터를 사용한다. 부분 수열의 시작과 끝 인덱스를 각각 lo, hi라 하자. 부분 수열의 시작과 끝 인덱스를 각각 lo, hi라고 두자. 수열이 비내림차순으로 정렬되어 있기 때문에 hi를 늘리면 무조건 sum(lo, hi)는 증가한다. 또한 모두 양수이므로 lo를 늘리면 무조건 sum(lo, hi)는 감소한다. 따라서 투포인터를 사용하여 O(N)에 해결할 수 있다. lo = 0, hi = 0인 경우부터 시작한다. 2. sum(lo, hi) < k 이면 hi를 늘린다. sum(lo, hi) < k이면 부.. 2023. 9. 5.
프로그래머스 두 원 사이의 정수 쌍 - C++ 풀이 1. -r2 ≤ k ≤ r2인 정수 k에 대해 x = k인 모든 점을 구한다. 2. 직선 x = k와 작은 원, 큰 원이 만나는 점의 양수 y 좌표를 각각 lo, hi라 하면 x = k인 점은 2 * (floor(hi) - ceil(lo) + 1)개이다. 3. | k | ≥ r1이면 2 * (floor(hi) + 1)개이다. 1. -r2 ≤ k ≤ r2인 정수 k에 대해 x = k인 모든 점을 구한다. x 좌표를 기준으로 -r2부터 r2까지 탐색하며 주어진 조건을 만족하는 점들의 개수를 구해나가자. 2. 직선 x = k와 작은 원, 큰 원이 만나는 점의 양수 y 좌표를 각각 lo, hi라 하면 x = k인 점은 2 * (floor(hi) - ceil(lo) + 1)개이다. 두 원 사이의 공간에 위치한 점.. 2023. 9. 5.
프로그래머스 요격 시스템 - C++ 풀이 1. 타겟들을 끝점 기준으로 오름차순 정렬한다. 2. 순차적으로 끝점에서 요격한다. 3. 만약 현재 타겟의 (시작점 > 마지막 요격점)인 경우, 새로 요격해야 한다. 1. 타겟들을 끝점 기준으로 오름차순 정렬한다. 먼저 타겟들을 끝점 기준으로 오름차순 정렬한다. 끝점의 x좌표가 작은 순서대로 처리하기 위함이다. 2. 순차적으로 끝점에서 요격한다. 요격 횟수를 최소화해야 하므로 한 번의 요격으로 최대한 많은 타겟을 처리해야 한다. 따라서 타겟의 최대한 끝점에서 요격해야 뒤에 있는 타겟들에 최대한 많이 걸칠 수 있다. 마지막 요격점은 기록해둔다. 3. 만약 현재 타겟의 (시작점 > 마지막 요격점)인 경우, 새로 요격해야 한다. 만약 현재 타겟의 시작점이 마지막 요격점보다 뒤에 있는 경우 요격 포인트안에 들어.. 2023. 9. 4.
반응형

티스토리툴바