MZ 개발자

원재가 어떤 물건을 조건 하에 사재기를 하려고 하는데 조건은 다음과 같다. 1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다. 2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다. 3. 판매는 얼마든지 할 수 있다. 예를들어 5일동안 물건의 매매가를 6 9 1 1 3 으로 알고있을때 조건을 만족했을때 최대로 얻을 수 있는 이득은 6을 사고 9에 팔고 1을 사고3에 팔아서 총 7만큼 최대 이익을 챙길 수 있다. 처음 문제를 보았을때 최대 이익을 얻기 위해서 우선순위 큐를 생각하였다. 하지만 이를 이용하면 인덱스의 순서가 바뀌게 되어 우선순위 큐를 관리해주어야 한다. 우선순위 큐를 이용하여 구현한 방식이다. #include #include #include #inclu..

이 문제의 접근 방법은 현재 가진 연료로 갈수 있는 주유소 중 멈췄을때 가장 많은 연료를 획득할 수 있는 주유소에서 멈추면 된다. 주유소의 위치가 순서대로 들어오지 않기 때문에 주유소 위치를 정렬 시켜주어야 한다. 이후 현재 가진 연료로 멈출 수 있는 모든 주유소에서 얻을 수 있는 연료의 양을 우선순위 큐에 넣고 빼면서 전체 획득한 연료 양을 누적시킨다. #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 일때 직선상으로 변환하면서 노선을 두개를 추가하였기 때문에 결과에는 중복된 값이 저장된다. 따라서 중복된 값을 ..

문제 풀이의 핵심은 한블럭 이동을 w 대각선 이동을 s라 할때 (0,0) 에서 (1,1)로 갈수 있는 방법중 최소시간을 우리는 구할 수 있다. 즉 s 와 2*w 중 걸리는 시간이 작은 것을 고르면 된다. 단순하게 생각하면 만약 대각선으로 움직이는 것이 직선으로 이동하는것보다 작을 경우 즉 s> x >> y >> w >> s; if(2 * w

문제의 힌트를 보면 잘 이해가 되지 않는다. 상식적으로 웅덩이를 덮을때 시작점에 딱 맞춰서 널빤지를 붙이면 최적이다. 힌트를 보면 웅덩이는 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