αλγριθμο

https://codeforces.com/contest/1557 Dashboard - Codeforces Round #737 (Div. 2) - Codeforces codeforces.com 처음으로 써보는 코드포스 후기입니다. 사진을 보시면 아시겟지만 일단 망쳤어요. 쓸데없는 변명을 하자면 암흑기가 온 것 같습니다... 어쨌든, 대회 때 푼 거랑 업솔빙해서 푼 거 합쳐서 3솔을 햇구요, 푼 문제의 풀이를 올려보려 합니다. A. Ezzat and Two Subsequences 사용한 알고리즘: 정렬, 누적합 풀이 입력받은 배열을 정렬하고 각 \(i\)번째와 \(i - 1\)번째 사이를 갈라 두 구간으로 나눠본 다음 두 구간합의 평균의 합중 최대값을 구하면 됩니다. \((1 < i \leq N)\) 왜 굳..

문제 https://www.acmicpc.net/problem/2984 2984번: 고속도로 상근이네 트럭 운송 회사가 내야하는 고속도로 이용 요금의 최솟값을 출력한다. 이 값은 32비트 정수 범위를 넘어갈 수 있기 때문에, 64비트 정수(C/C++: long long)을 사용해야 한다. www.acmicpc.net 알고리즘 DP 풀이 입력에서 맨 처음에 \(N\)을 입력받은 후, \(N\)개의 쌍이 주어지는데, 각 \(i\)번째 쌍에서 첫 번째 수를 \(a_i\), 두 번째 수를 \(b_i\)라고 하겠습니다. 이번 문제는 간단하게 말하자면 입력받은 배열 \(a\)와 \(b\)를 적절히 재배치해서 새로운 쌍들을 만들었을 때 각 쌍의 두 수의 차의 합이 최소가 되게끔 만드는 문제입니다. 그냥 두 배열을 정..

문제 https://www.acmicpc.net/problem/1126 1126번: 같은 탑 첫째 줄에 조각의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 각 조각의 높이가 주어진다. 높이는 500,000보다 작거나 같은 자연수이고, 모든 조각의 높이의 합은 500,000을 넘 www.acmicpc.net 알고리즘 DP 배낭 문제 슬라이딩 윈도우 (optional) 풀이 \(N\)개의 직사각형 블록을 이용하여 만든 높이가 같은 두 탑의 높이가 최대가 되게 해야 하며, 모든 직사각형 블록을 다 사용할 필요는 없습니다. 즉, \(i\)번째 직사각형 블록을 쌓거나 쌓지 않거나로 나눌 수 있습니다. 그러므로, \(dp[i][j]\)를 다음과 같이 정의할 수 있습니다: \(dp[i][j..

문제 https://www.acmicpc.net/problem/5444 5444번: 시리얼 넘버 위대한 기타리스트 강토는 공연을 앞두고 있다. 이제 무대에 올라가야 하는데, 기타가 다른 사람들의 기타와 섞이고 말았다. 또, 강토는 어떤 기타가 자기 것인지 까먹었다. 다행히도, 모든 기타 www.acmicpc.net 알고리즘 DP 슬라이딩 윈도우 풀이 각 테스트케이스마다 \(N\)개의 시리얼 넘버 \(S_{1} ... S_{N}\)과 \(M\)이 주어졌을 때 \(dp[i][j]\)를 다음과 같이 정의할 수 있습니다: \(dp[i][j]:\) \(i\)번째 기타까지 고려했을 때 시리얼 넘버의 합을 \(M\)으로 나눈 나머지가 \(j\)가 되게 하는 기타의 최대 개수. 위와 같이 정의한다면, \(dp[i][j..

문제 https://www.acmicpc.net/problem/2315 2315번: 가로등 끄기 첫째 줄에는 2개의 정수 N(1 ≤ N ≤ 1,000), M 이 있다. 첫 번째 정수 N은 가로등의 개수를 나타내는 정수이고, 두 번째 정수 M은 마징가 처음에 위치하는 가로등 번호이다. 다음 N 개의 줄에는 각 가 www.acmicpc.net 알고리즘 DP 누적 합 풀이 만약, \(i\)번째 가로등에서 \(j\)번째 가로등을 끄기 위해 이동한다면, 두 가로등 사이에 있는 가로등은 지나가면서 끄는게 가장 효율적입니다. 그러므로, \(i\)번째와 \(j\)번째 가로등이 꺼져 있다는 것은, 두 가로등 사이의 가로등도 꺼져 있다는 뜻입니다. 따라서, 가로등에 대한 정보가 주어졌을 때, 다음 \(3\)개의 배열을 만..

문제 https://www.acmicpc.net/problem/2647 2647번: 검은점과 하얀점 연결 2n개의 점이 x축의 좌표 1,2,...2n에 놓여 있다. 그 중 n개는 검은 점이고, n개는 하얀 점이다. 하나의 검은 점과 하나의 하얀 점을 연결하여 한 쌍을 만들면, 모두 n개의 쌍이 만들어진다. 한 쌍의 점 www.acmicpc.net 알고리즘 DP 풀이 DP 역추적 문제입니다. 점들에 대한 정보가 주어졌을 때, 다음 \(3\)개의 배열을 만들어 정의할 수 있습니다: \(dp[i][j]:\) \(i\)번째부터 \(j\)번째까지의 점으로 길을 만들 때, 길의 거리의 합의 최솟값. \(hgt[i][j]:\) \(i\)번째부터 \(j\)번째까지의 점으로 길을 만들 때, 높이가 가장 높은 길의 높이(..

문제 https://www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5≤N≤1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1≤W≤1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 www.acmicpc.net 알고리즘 DP 풀이 점화식을 세우는 것이 조금 어려웠습니다. 하지만 점화식만 잘 세우면 구현과 역추적은 쉽습니다. 배열 \(2\)개를 만들어 다음과 같이 정의합니다; \(dp[i][j]:\) 두 경찰차가 마지막으로 처리한 사건이 각각 \(i, j\)일 때(두 경찰차의 위치가 각각 사건 \(i\), 사건 \(j\)의 위치일 때), 마지막으로 처리된 사건의 다음 사건부터 마지막 사..

문제 https://www.acmicpc.net/problem/17422 17422번: 지폐가 넘쳐흘러 첫째 줄에 금고의 개수 N이 주어진다. 양의 정수 k에 대해, N = 2k-1이 항상 성립한다. 둘째 줄에 금고에 들어 있는 지폐의 개수 Wi가 1번 금고부터 순서대로 주어진다. 셋째 줄에 놀이의 횟수 Q가 www.acmicpc.net 알고리즘 트리DP 우선순위 큐 풀이 트리와 각 금고의 지폐의 개수 \(W_{i}\)가 주어졌을 때, 두 배열 \(A, B\)를 만들어 다음과 같이 정의합니다: \(A_{i}:\) \(i\)을 루트로 하는 서브트리 안에 있는 한 리프 노드로부터 \(n\)까지의 경로에 있는 지폐 개수의 최대값. \(B_{i}:\) \(i\)을 루트로 하는 서브트리 안에 있는 지폐 개수의 합..