oVeron

https://www.acmicpc.net/problem/1071 1071번: 소트 N개의 정수가 주어지면, 이것을 연속된 두 수가 연속된 값이 아니게 정렬(A[i] + 1 ≠ A[i+1])하는 프로그램을 작성하시오. 가능한 것이 여러 가지라면 사전순으로 가장 앞서는 것을 출력한다. www.acmicpc.net 주어진 수를 중복되지 않게 정렬해 보자. 예제 5의 경우 (1, 2, 3)과 같이 정렬될 것이다. 이 문제의 해법은 간단한데, 이렇게 정렬한 인접한 수가 조건에 위배되면, 인접한 수 중 큰 수보다 더 크면서 가장 작은 수 하나를 사이에 끼워넣는 것이다. (1, 2, 3)의 경우 (1, 2)가 조건에 위배되므로 그 사이에 2보다 크면서 가장 작은 수인 3을 끼워넣는다. 그 후 1의 개수만큼 1을 출..

알고리즘/baekjoon 2023. 6. 5. 11:38

https://www.acmicpc.net/problem/27384 27384번: Beast Bullies There are some animals with distinct strength levels getting water from a watering hole. The more animals that are at the watering hole the less water each animal will get. For this reason some of the animals will try to force the others to leave. Periodic www.acmicpc.net 힘이 약한 순으로 동물들이 잡아먹히므로, 역으로 힘이 가장 큰 동물 두 마리만 남아 있다 생각해 보자. 예제 1에서 ..

알고리즘/baekjoon 2023. 6. 5. 11:22

https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들 www.acmicpc.net 관찰 1. 각 조마다 최대 키와 최소 키의 차이가 최소가 되어야 하므로, 이를 쉽게 구하기 위해 우선 원생들의 키를 오름차순 정렬하자. 그 후 조를 짤 때 반드시 연속해서 존재하는 원생들을 선택해야 한다. 그렇지 않을 때의 최대 키와 최소 키의 차이가 연속해서 존재하는 원생들을 선택할 때보다 무조건 클 수밖에 없기 때문이다. 2. 각 조에서 최대 키와 최소 키의 차이를 구하..

알고리즘/baekjoon 2023. 5. 5. 12:22

https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 2개 회의실로 3개 회의를 모두 진행할 수 있다. 예를 들어, 첫번째 회의실에서 첫번째 회의를 진행하고 두번째 회의실에서 두번째 회의와 세번째 회의를 진행하면 된다. 1개 회의실로 3개 회의 www.acmicpc.net 하나의 회의실에 최대한 많은 회의를 배정해야 회의실 수를 최소화할 수 있다. 1. 시작 순서 -> 끝 순서로 정렬되는 우선순위 큐(meetingTime)에 입력값을 push한다. 2. 끝 순서를 오름차순 정렬하는 우선순위 큐 endTime에 - endTime이 비어있다면 : push - 아니라면 : - 가장 빨리 끝나는 시간이 시작 시간보다 작다면, 그 빨리 끝나는 시간을 pop한다. pu..

알고리즘/baekjoon 2023. 3. 9. 00:59

https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 예제 입력 1의 첫 번째 테스트케이스를 살펴보자. 해당 테스트케이스에서 순서쌍 (3, 4)만 순위가 바뀐 쌍이라 해 보자. 이때 답은 IMPOSSIBLE이 아니다. 3과 4 사이에 끼어있는 팀이 존재하지 않기에, 3번 팀과 4번 팀의 순위를 바꿔도 영향을 받는 팀이 없기 때문이다. 이번에는 해당 테스트케이스에서 순서쌍 (2, 4)만 순위가 바뀐 쌍이라 해 보자. 이때 답은 IMPOSSIBL..

알고리즘/baekjoon 2023. 3. 2. 17:10

https://www.acmicpc.net/problem/25709 25709번: 1 빼기 민겸이는 1 빼기를 할 수 있는 능력을 가지고 있다. 1 빼기란, 다음의 두 연산 중 하나를 골라 수행하는 것이다. 가지고 있는 수에서 1을 뺀다. 가지고 있는 수에 있는 1을 하나 지운다. 지우고 난 www.acmicpc.net 1이 존재하면 무조건 1을 지우고, 그 외에는 1을 빼주면 된다. #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair pii; int N; int ans{ 0 }; int main(..

알고리즘/baekjoon 2023. 2. 6. 00:07

https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net gi가 입력될 때, gi보다 작되 가장 큰 공항을 골라야 최대한 많은 비행기를 도킹시킬 수 있다. 하지만 평범하게 이를 구현하면 시간초과가 나므로, 유니온 파인드를 이용해 gi보다 작되 가장 큰 공항을 부모로써 가지게 설계하면 된다. #include #include #include #include #include #include #include #include #..

알고리즘/baekjoon 2023. 1. 30. 19:48