전체 글
-
백준 20106: Cave코딩 2022. 2. 23. 20:40
https://www.acmicpc.net/problem/20106 20106번: Cave While lost on the long walk from the college to the UQ Centre, you have stumbled across the entrance to a secret cave system running deep under the university. The entrance is blocked by a security system consisting of N consecutive doors, each door behind www.acmicpc.net 번역본은 https://oj.uz/problem/view/IOI13_cave를 참고하시면 됩니다. 풀이 시행이 최대 70,000번이며..
-
백준 20085: Detecting Molecules코딩 2022. 2. 22. 23:37
https://www.acmicpc.net/problem/20085 20085번: Detecting Molecules C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang) www.acmicpc.net 혹시라도 번역이 귀찮고 궁금하다면 https://oj.uz/problem/view/IOI16_molecules을 보는 것도 좋습니다. 풀이 굉장히 많은 생각을 하다 보면, 재미있는 관찰이 가능해집니다. "문제의 조건을 만족하는 해가 존재한다는 것과 정렬된 배열 w에서 연속된 값들의 합 중 문제 조건을 만족하는 값이 있다는 것은 동치이다." 문제의 처음이자 끝인 관찰이고, 저로서는 생각해내는 것이 어려웠습니다. 위의 명제를 증명해보겠습니다. 더보기..
-
백준 21761: 초직사각형코딩 2022. 1. 28. 14:58
https://www.acmicpc.net/problem/21761 21761번: 초직사각형 1차원 공간에서의 선분, 2차원 공간에서의 직사각형, 3차원 공간에서의 직육면체를 생각해 보자. 선분의 크기는 변수 $A$로, 직사각형의 크기는 두 개의 변수 $A$와 $B$로, 직육면체의 크기는 세 개 www.acmicpc.net 풀이 적당히 눈에 보이는 그리디로 풀어주면 맞습니다. $ABCD$의 값을 최대로 변화시켜주는 카드를 계속 찾아주면 됩니다. 이 방법으로 최적해를 찾을 수 있다는 것을 증명해보겠습니다. 더보기 처음에 값이 $A,\ B,\ C,\ D$라고 하겠습니다. 첫 시행에서 초직사각형의 부피를 가장 많이 증가시켜주는 카드를 일반성을 잃지 않고 $A$를 $N$만큼 증가시켜주는 카드(이제부터 $X$라고..
-
백준 1115: 순열코딩 2022. 1. 13. 14:32
https://www.acmicpc.net/problem/1115 1115번: 순열 0부터 N-1까지 모든 정수를 한 번씩 포함하고 있는 순열 A[0], A[1], ..., A[N-1]이 있다. 순열 A를 이용해서 A와 길이가 같은 자식 배열 B을 아래와 같은 방법으로 구할 수 있다. B[0] = 0 B[i] = A[B[i-1]] (1 ≤ www.acmicpc.net 풀이 순열 $A$를 $i \ \rightarrow \ A[i]$인 유향그래프처럼 생각해 봅시다. $A$에 $0\sim N-1$의 수가 모두 하나씩 들어가 있으므로 모든 노드들은 indegree와 outdegree가 각각 1이 됩니다. 따라서 이 그래프는 사이클로만 이루어지게 됩니다(증명은 귀류법으로 쉽게 할 수 있으므로 생략합니다). 이 사..
-
백준 12987: Matrix Again코딩 2021. 12. 9. 21:47
https://www.acmicpc.net/problem/12987 12987번: Matrix Again 첫 번째 줄에 N, K, M (1 ≤ N ≤ 50, 1 ≤ K ≤ 109, 1 ≤ M ≤ 104) 이 공백을 구분으로 주어집니다. 다음 N개의 줄에 걸쳐 행렬 A가 주어집니다. (-104 ≤ Aij ≤ 104, 1 ≤ i, j ≤ N) www.acmicpc.net 풀이 분할 정복을 이용하여 쉽게 풀 수 있습니다. $S_T=A+A^2+\dots+A^T$라고 하고, $S_T$를 빠르게 구해 봅시다. $S_{T/2}=A+A^2+\dots+A^{T/2}$이기 때문에, $T$가 짝수일 땐 $S_T=S_{T/2}+A^{T/2}\times S_{T/2}$로 $S_T$를 구할 수 있고, $T$가 홀수일 땐 $S_T..
-
Codeforces Round #752 (Div. 2)코딩 2021. 11. 1. 18:33
이번에 CR#752에서 314등으로 퍼플퍼포가 되었고, +110이 되어 코드포스 블루에 드디어 도달했습니다. 아무래도 운이 많이 따른 라운드인 것 같습니다. D는 그냥 수학문제였고, C는 나이브로 풀었지만 시스텟에서 다행히도 TLE가 나지 않았습니다(아니면 TLE날 데이터가 원초 없었을 지도 모르겠네요). 이대로 끝내기는 뭐하니까 이미 에디토리얼은 나왔지만 그냥 풀이를 쓰겠습니다. A. Era $a[i]-i$의 max를 찾으면 끝나는 문제입니다. 더보기 #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int T; cin >> T; while(T--) { int n, a[101], m=0; cin >> ..
-
백준 7812: 중앙 트리코딩 2021. 9. 16. 13:53
https://www.acmicpc.net/problem/7812 7812번: 중앙 트리 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 트리의 정점의 수 n이 주어진다. (1 ≤ n ≤ 10,000) 각 정점은 0번부터 n-1번까지 번호가 붙여져 있다. 다음 n-1개 줄 www.acmicpc.net 풀이 $O(N^2)$으로는 TLE를 받게 됩니다. 따라서 이보다 더 빠른 코드를 찾아야 하고, 트리 dp를 생각해봤을 때 $O(N)$의 풀이를 찾을 수 있습니다. 문제의 예제 입력 테스트 케이스 1번을 봅시다. 편의를 위해 0번 노드를 루트 노드로 잡겠습니다. $dp[i]=(i$번 노드에서 모든 정점으로 이르는 비용의 합$)$이라 합시다. 이 식을 가지고 자식 노드와 부모 노..
-
백준 7453: 합이 0인 네 정수코딩 2021. 8. 13. 14:13
https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 풀이 A[a], B[b], C[c], D[d]의 모든 경우를 다 세어본다면 시간복잡도가 $O(N^4)$이지만, $N\leq 4000$이므로 12초 안에 해결할 수 없습니다. 그러면 Meet in the middle 알고리즘으로 시간복잡도를 줄여보겠습니다. 우선 A의 모든 원소와 B의 모든 원소의 합을 담은 배열 AB, C의 모든 원소와 D의 모든 원소의 합을 담은 배열을 CD라 ..