그리디

1. 개요 안녕하세요. 이 문제의 유형은 비트마스킹 + 그리디입니다. 저는 그리디만을 사용해서 풀이했습니다. 납득이 되는 풀이는 사실 비트마스킹을 사용하는 방법인데요. 저는 빙빙 돌아서 그리디만 사용했습니다. 2. 문제풀이 N개의 물병과 한 번에 들 수 있는 물병의 개수 K가 주어집니다. 물병을 합치는 로직은 결국 이진수의 원리와 같습니다. 물병 안에 차있는 물은 항상 2의 거듭제곱만큼만 채울 수 있죠. 저는 K - 1번의 루프를 통해 N보다 작거나 같은 2의 거듭제곱 중 가장 큰 수를 골라 N에서 빼주었습니다. 이는 K - 1개의 물통에 채울 물을 결정하는 로직입니다. 남은 물의 양 X가 2의 거듭제곱이거나 0이면 상점에서 물을 구매할 필요가 없고, 2의 거듭제곱이 아니라면 남은 물의 양보다 큰 2..

1. 개요 안녕하세요. 이 문제의 유형은 그리디입니다. 이 문제는 유형을 구분하기에도 조금 힘들었던 문제였습니다. 이유는 발상이 어려운데요. 문제의 데이터 크기 조건을 확인하지 않으면 knapsack 문제로 해석도 가능합니다. 가능한 모든 데이터가 10억이라 DP로 풀이할 시 MLE와 TLE를 피할 수 없습니다. 2. 문제 풀이 우선 입력으로 들어오는 저울추의 무게를 오름차순으로 정렬합니다. 그 다음 만들 수 있는 숫자의 범위를 결정해야 합니다. 만들 수 있는 최소 무게는 모든 저울추를 제외한 경우인 0입니다. 따라서 처음 가능 범위는 [ 0, 1 )입니다. 이제 정렬된 저울추의 무게 리스트를 순회하면서 무게 1을 만들 수 있는지 비교해야 합니다. 1이 아닌 임의의 자연수 K에 대해서 [ 0, K ..

1. 개요 안녕하세요. 오늘 문제의 유형은 그리디입니다. 저는 이 문제를 naive하게 풀었다고 생각했는데 AC를 받아버렸습니다. 제가 푼 방법이 그리디하게 풀 수 있는 방법이었나봅니다. 2. 문제 풀이 방법은 단순합니다. 현재 들여쓰기 칸 수를 저장하는 배열 a와 올바른 들여쓰기 칸 수를 저장하는 배열 b가 있다고 했을 때, 0  3. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector vl;typedef vector vp..

1. 문제 풀이 문제 유형은 그리디입니다. 코드포스에서 나올법한 문제였습니다.  정수 N, K에 대해서 임의의 문자열 S는 다음과 같은 조건을 만족합니다.문자열 S의 길이는 N이고, 'A' 또는 'B' 문자로만 이루어져 있다.문자열 S는 0 N, K를 입력받은 다음, 'B'로만 이루어진 길이 N의 문자열을 선언합니다.루프를 돌면서 현재 위치 idx에 대해서 S[idx]를 A로 바꾸었을 때, 두 번째 조건을 만족하는 쌍이 몇 개 나오는지 검사합니다. 여기서 [ 0, idx ) 구간에서 'A'로 바꾼 횟수를 세어야 합니다. S[idx] 문자를 'B'에서 'A'로 바꾸게 된다면 이전에 계산했었던 쌍의 개수가 변동되기 때문 AABBB는 2 번째 조건을 만족하는 ( i , j ) 쌍이 6개 존재합니다. 여기서 A..

1. 문제 풀이 미리 기지국이 설치된 곳을 기준으로 구역이 나뉘게 됩니다. 그 구역별로 따로 계산을 해야 일관성을 가질 수 있다고 추측하였습니다. 따라서 구역을 구분하는 작업을 먼저 합니다. 여기서 주의할 점은 미리 설치된 기지국들은 서로 인접한 곳에 위치할 수 있다는 가능성입니다. 예를 들어, stations[i] 위치에 설치된 기지국의 전파가 닿는 위치에 stations[i + 1]이나 stations[i - 1] 등이 설치될 가능성을 배제할 수 없습니다. 따라서 각 statons의 위치 cx와 전파 거리 w에 대해서 {cx - w, cx + w}와 같은 line을 만들어 저장한 다음 그리디하게 선들을 merge하는 작업을 했습니다. 이로써 기지국의 전파가 닿지 않는 구역들이 구분되고 각 구역의 크기..

1. 문제 풀이 각 차량의 진출 지점에 대해서 내림차순으로 정렬합니다. 첫  단속카메라를 설치해야할 지점은 먼저 나간 차량의 진출 시점입니다. 그 후, 순회하면서 각 차량들의 진입, 진출 시점 사이의 단속카메라가 위치해있는지 확인하고 만약 없다면 그 차량의 진출 시점에 새로운 카메라를 설치해야합니다. 2. 코드#include using namespace std;using pi = pair;#define X first#define Y secondvector lines;int solution(vector> routes) { for(auto &cur : routes) { lines.push_back({cur[1], cur[0]}); } sort(lines.begin(), l..

1. 문제 풀이gi가 주어졌을 때 1번부터 gi 중 아직 도킹하지 않은 게이트를 찾는 쿼리를 최적화하는 것이 중요한 문제 같습니다. 배열 p의 값을 p[x] = x를 가지게 한 다음 유니온 파인드의 경로 압축을 응용하여 도킹할 게이트를 찾게 하여 최적화하였습니다. p[x] = x인 값을 찾으면 아직 도킹하지 않은 게이트 번호입니다. 도킹을 시도한 다음 p[x]를 1 감소하여 p[x]를 x-1로 갱신해 p[x-1]에서 게이트 번호를 찾게끔 구현하였습니다. 이 때 찾은 번호가 0이면 더 이상 도킹이 불가능하다는 base condition도 추가하였습니다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull..

1. 문제 풀이 배열을 { 값, 순서 } 형태로 저장합니다. 여기서 값은 배열의 실제 값이고, 순서는 해당 값이 배열에서 등장한 순서를 의미합니다. 이 배열을 값을 기준으로 내림차순으로 정렬하되, 값이 같다면 순서를 오름차순으로 정렬합니다. 정렬한 두 배열의 처음 값을 가리키는 포인터를 각각 두고, 두 포인터 중 하나가 배열의 끝에 도달할 때까지 비교를 진행합니다. 두 포인터가 가리키는 값 중 더 큰 값을 가진 포인터를 앞으로 이동시킵니다. 과정을 진행하다가 두 포인터가 가르키는 값이 서로 같아지면 해당 값이 지금까지 저장한 부분 수열의 마지막 값의 순서보다 나중에 등장한 값이라면 그 값을 부분 수열에 추가합니다. 그렇지 않다면 버리고, 계속 진행합니다. 여기서 중요한 점은, 부분 수열에 값을 추가할 때..