전체 글
항공대 알고리즘 동아리 Koala 🥰
youtu.be/HSQ77EeiiaI
2346번: 풍선 터뜨리기 첫째 줄에 자연수 N(1≤N≤1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 편의상 0은 적혀있지 않다고 가정하자. www.acmicpc.net 큐, 덱으로는 돌아가는 식의 문제를 내는 것이 국룰인것 같습니다. 이 문제도 반전 요세푸스와 풀이 과정은 비슷하나, 첫 입력 인덱스를 기억해야 한다는 것이 까다롭습니다. 그래서 pair로 덱에 입력을 받겠습니다. 비교할 때는 first를 통해 비교하고, 출력할 때는 second를 출력할 것입니다. [정답코드 보기] #include #include #include #include #include #include #include #include #include using namespace std..
출처 : www.acmicpc.net/problem/13975 문제 여러 장의 소설이 각각 다른 파일에 저장되어 있다. 소설을 모두 쓰면, 각 장이 쓰인 파일을 합쳐 최종적 완성본인 단 하나의 파일만을 남겨두어야 하는데, 이 과정에서 두 개의 파일을 합치고, 합친 파일이나 다른 두 개의 파일을 계속 두 개씩 합쳐나가야 한다. 두 개의 파일을 합칠 때 필요한 비용이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총합을 계산하시오. ex. 40, 30, 30, 50 -> 40, (30 + 30), 50 -> (40 + 50), 60 -> 90, 60 -> 150 이때, 비용은 60 + 90 + 150 = 300 이 된다. 풀이 더보기 우선순위 큐를 사용하는 아주 웰 ..
출처 : www.acmicpc.net/problem/1477 문제 다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다. 이 때 세울 수 있는 휴게소의 조건은 다음과 같다. 이미 휴게소가 있는 위치는 세울 수 없다. 고속도로의 마지막 점에 세울 수 없다. 정수 위치에만 세울 수 있다. M개의 휴게소를 적절히 배치하여 휴게소가 없는 구간의 최댓값을 최소로 만들어라. 풀이 더보기 이 문제는 휴게소가 없는 구간의 최댓값을 이분 탐색으로 시뮬레이션하는 방법이 있긴 하나, 여기서는 우선순위 큐를 이용해 풀어보겠습니다. 우선 단순하게 생각해서 풀이를 떠올려..
출처 : www.acmicpc.net/problem/7662 문제 이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다. 주어진 정수 값 자체를 우선순위라고 했을 때, 주어진 ..
. youtu.be/iFv7eadVhwk youtu.be/t7-4E4WBFJQ
문제링크 codeforces.com/contest/1481 Dashboard - Codeforces Round #699 (Div. 2) - Codeforces codeforces.com A. Puzzle From the Future 문제 우주선으로 (0,0)에서 (px, py)로 이동하려고 한다. 우주선은 문자열 s에 입력된대로만 이동할 수 있고, 우주선이 문자열을 읽는 순서는 왼쪽에서 오른쪽으로 읽는다. 현재 좌표가 (x,y)이고, 읽어야하는 문자열의 위치가 s[i]일 때, 아래와 같은 규칙으로 이동한다고 한다. - s[i] == U이면 (x, y) -> (x, y+1)로 이동 - s[i] == D이면 (x, y) -> (x, y-1)로 이동 - s[i] == R이면 (x, y) -> (x+1, y)로..
http://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 전체 코드 더보기 #include #include using namespace std; const int MAX = 10000; int N, M; int num[MAX]; bool calc(int mid) { int sum = 0; for (int i = 0; i N; for (int i = 0; i < N; i+..
www.acmicpc.net/problem/2980 2980번: 도로와 신호등 상근이는 트럭을 가지고 긴 일직선 도로를 운전하고 있다. 도로에는 신호등이 설치되어 있다. 상근이는 각 신호등에 대해서 빨간 불이 지속되는 시간과 초록 불이 지속되는 시간을 미리 구해왔 www.acmicpc.net 전체 코드 더보기 #include #include using namespace std; int n, l; map mp; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> l; for (int i = 0; i > d >> r >> g; mp[d] = make_pair(r, g); } int dis..
www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 전체 코드 더보기 #include #include #include #include using namespace std; typedef long long ll; int n; vector v; int dp[10001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); memset(dp, 0, sizeof(dp)); cin >> n; v.resi..