전체 글36 CF 1741D https://codeforces.com/contest/1741/problem/D Problem - D - Codeforces codeforces.com 풀긴 했는데 풀이가 더러워서 다시 풂 분할 정복 현재 인덱스 범위 [l, r], 현재 숫자 범위 [nl, nr] 1) l == r 이면 arr[l]이 nl과 같아야 함. 2) arr[l]이 nmid 보다 크면 왼쪽 구간과 오른쪽 구간에 대해 분할 정복 후 둘을 뒤집어야 하므로 1을 더함. 3) 작으면 똑같이 분할 정복 후 둘을 뒤집을 필요가 없으므로 0을 더함. 불가능하면 종료 조건인 l == r 에서 알아서 걸러지므로 따로 또 뭘 할 필요가 없다(왼쪽 구간과 오른쪽 구간을 정렬 후 합치기 등). 2022. 10. 12. BOJ 24493 https://www.acmicpc.net/problem/24493 24493번: Cereal 2 Print the minimum number of cows that go hungry, followed by any permutation of $1\ldots N$ that achieves this minimum. If there are multiple permutations, any one will be accepted. www.acmicpc.net 반례가 자꾸 나와서 12번 제출해서 맞은 문제 시리얼을 정점, 소를 간선으로 보고 (f[i], s[i])를 이어준다. (간선 방향은 상관 없음. 일단 무방향으로 다 이어준다.) 다른 연결요소들 끼리는 배치 순서가 상관이 없으므로 각 연결요소 안에서만 생각하면 .. 2022. 10. 2. CF 1733D2 https://codeforces.com/contest/1733/problem/D2 Problem - D2 - Codeforces codeforces.com 느리게 풂 + 튜토리얼이랑 내 풀이랑 달라서 기록 내 풀이 먼저 a랑 b에서 다른 인덱스를 배열 arr에 저장. arr.sz가 홀수면 불가능. 1) arr.sz = 2 arr[1] - arr[0] = 1 이면 min(x, y * 2) 아니면 min((arr[1] - arr[0]) * x, y) 2) arr.sz > 2 dp[cur][cnt] : cur ~ sz - 1 중에 인접한 원소 둘을 x만 이용해서 cnt / 2번 묶을때의 최소값. dp[cur][cnt] = min(dp[cur + 1][cnt], dp[cur + 2][cnt - 2] + (ar.. 2022. 10. 2. BOJ 22595 https://www.acmicpc.net/problem/22595 22595번: Sightseeing Tour The first line contains the number of sightseeing area N (1 ≤ N ≤ 100). Next N lines describe the integer matrix C, where the j-th element of the i-th row of the input describes Ci,j (0 ≤ Ci,j ≤ 1, 000, 000). For each i, you can assume Ci,i is alwa www.acmicpc.net xhdtlsid2 가 풀이 알려줬다. 그냥 어떻게 지우던 항상 경로가 존재해서 비용 작은 것만 골라서 지우면 됨. 대충 귀납법.. 2022. 10. 1. 이전 1 ··· 3 4 5 6 7 8 9 다음