MZ 개발자

이 문제의 접근 방법은 현재 가진 연료로 갈수 있는 주유소 중 멈췄을때 가장 많은 연료를 획득할 수 있는 주유소에서 멈추면 된다. 주유소의 위치가 순서대로 들어오지 않기 때문에 주유소 위치를 정렬 시켜주어야 한다. 이후 현재 가진 연료로 멈출 수 있는 모든 주유소에서 얻을 수 있는 연료의 양을 우선순위 큐에 넣고 빼면서 전체 획득한 연료 양을 누적시킨다. #include #include #include #include using namespace std; priority_queue pq; vector v; int n; int l, p; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n; for(int i = 0; i < n; i..

처음 생각한 방법은 노선 길이가 가장 긴 구간부터 구간에 겹치는지 안겹치는지 확인하려고 하였다. 여기서 발생한 문제는 정류소의 갯수가 3 ~ 1,000,000,000개 이기 때문에 모든 정류소를 배열로 정의할 수 없다. 따라서 어떤 노선이 다른 노선에 포함되는지 안되는지 한번에 알수 있는 방법이 필요하다. 만약 모든 노선 a,b에서 ab 라면 조금 복잡하다. 예를들어 [0~3]와 [9~4]는 위의 방법을 적용할 수 없다. 위의 방법을 적용한다면 겹치는 노선임에도 불구하고 겹치지 않는 유효한 노선이 되버린다. 이를 해결하기 위해 노선을 직선상으로 바꿔보자. a>b 일때 ab 인 모든 노선을 ab 일때 직선상으로 변환하면서 노선을 두개를 추가하였기 때문에 결과에는 중복된 값이 저장된다. 따라서 중복된 값을 ..

문제의 힌트를 보면 잘 이해가 되지 않는다. 상식적으로 웅덩이를 덮을때 시작점에 딱 맞춰서 널빤지를 붙이면 최적이다. 힌트를 보면 웅덩이는 1에서 시작하는데 널빤지를 0에서 부터 붙이기 시작하여 사실상 힌트 오류라고 할수 있다. 실제 맞는 예시는 다음과 같다. .111222.333444555 .MMMMM..MMMM.MMMM 풀이 방법은 각 웅덩이 위치를 백터 v에 넣어 정렬한 후 각 웅덩이 마다 깔수 있는 널빤지를 구해주면 된다. 핵심은 널빤지가 다른 웅덩이를 일부 덮는다면 거기서부터 계속 붙여나가고, 그렇지 않고 널빤지의 끝이 일반 땅이라면 그다음 웅덩이부터 다시 붙여나가면 된다. #include #include #include using namespace std; int main() { ios_bas..

이 문제는 0을 뒤집거나 1을 뒤집어서 최소한의 뒤집기로 같은 숫자를 만드는 문제이다. 따라서 0과 1이 바뀌는 구간을 기준으로 0인 구간의 갯수과 1인 구간의 갯수중 최소인 숫자를 뒤집으면 답이된다. 예를들어 0001100의 경우 0의 구간은 앞쪽 000, 뒷쪽 00으로 총 2번 뒤집어야한다. 하지만 1의 구간의 경우 가운데 11으로 1번만 뒤집으면 된다. 따라서 최소한으로 뒤집어야하는 횟수는 1이 된다. #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); string s; cin >> s; int oneCnt = 0, zeroCnt = 0; for(int i..

S는 서로 다른 N개의 자연수의 합이기 때문에 N은 1부터 증가하면서 누적 합이 S를 초과하기 전의 N을 구하면 되는 문제이다. 하지만 S의 범위는 int를 초과하는 범위이기때문에 long long으로 바꿔주어야한다. #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); long long s; cin >> s; long long sum = 0; long long answer = 0; for(long long i = 1; ; i++) { if(sum + i

이 문제의 핵심은 모든 통나무 조각 길이보다 큰 경우를 만족하는 적절한 길이의 통나무를 구하는 문제이다. 예를들어 L =9, K=2, C=1 일 경우 나올수 있는 통나무 조각은 4,1,4이다. 이때 모든 통나무 조각 길이 보다 긴 적절한 길이의 통나무를 구해야한다. 우리가 생각해야하는 조건은 두가지이다. 1. 모든 잘린 통나무 조각은 적절히 자를수 있는 최대 길이(mid)로 모두 자를 수 있어야 한다. 2. 자를수 있는 횟수를 초과 하면 안된다. 이를 바탕으로 풀이를 다음과 같이 생각해볼 수 있다. 1. 만약 잘린 통나무 누적 길이가 mid보다 커지는 순간까지 cut을 하지 않고, 커지는 순간 cnt을 증가시켜준다. 2. 이후 마지막으로 누적한 통나무의 길이가 mid 보다 클경우 위의 조건 1을 만족하지..

가장 기본적인 그리디를 연습할 수 있는 문제이다. 조금더 실전과 같은 훈련을 하기 위해 타이머를 설정하고 문제를 풀었다. 비교적 쉬운 난이도여서 약 8분정도 만에 문제를 해결하였다. 풀이방법은 N개의 동전을 가치가 가장 큰 순서대로 정렬을 한다. 그리디는 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 따라서 동전 개수를 최소한으로 하기 위해 선택의 순간마다 가치의 합 K를 결정할때 K보다 작은 동전중 가장 큰 가치를 가진 동전을 선택하면 된다. 예를들어 예시가 다음과 같이 주어졌을경우 10 4200 1 5 10 50 100 500 1000 5000 10000 50000 4200원 보다 작은 동전 중 가치가 가장 큰 1000을 고르면 된다. 이후 1..

첫째 줄에 물이 새는 곳의 개수 N과 테이프 길이L 이 주어진다. 풀이방법은 시작점(start)을 잡고 시작점을 기준으로 물이 새는 곳(v[i]) 까지 거리가 L > n >> l; for(int i = 0; i > num; v.push_back(num); } if(l == 1) { cout

NxN 행렬로 동전이 앞 뒤로 놓여 있고 1번 연산에 행 또는 열 전체를 뒤집을 수 있다. 이때 뒷면이 위를 향하는 동전의 개수를 최소로 하는 연산의 수를 구하는 문제이다. 이 문제를 완전 탐색을 한다면 행을 바꿀때마다 열의 상태도 같이 변한다. 따라서 행을 바꾸는 경우의수 2^20, 열을 바꾸는 경우의수 2^20 총 2^40이 된다. 루트포스 알고리즘을 이용하여 완전 탐색을 한다면 시간 초과 발생 핵심은 우리의 목표는 T가 최소가 되도록 뒤집어야 한다. 만약에 어떤 상태를 미리 알 수 있다면 그 상태에서 어떤 행 또는 열을 뒤집을지 빠르게 판단할 수 있다. 여기서 어떤 상태를 미리 알기위해 비트마스킹 개념을 도입한다. 비트마스킹이란 n

동전의 갯수가 최소가 되기 위해 5원짜리를 최대한 많이 사용하여 거슬러주면된다. 하지만 여기서 핵심은 무조건 5원짜리를 가자 많이 사용한다고 최대가 되지 않는다. 예를들어 13원일 경우 5원 2개로 거슬러주면 나머지 3원은 2원 짜리로 거슬러 줄 수 없다. 따라서 5원 1개 2원 4개 총 5개의 동전이 최소가 된다. #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; int result = 99999999; for(int i = 0; i n) { cout