반응형 알고리즘 썸네일형 리스트형 [Codeforces] Round #694 (Div. 2) 풀이 2021. 01. 05 23:35 본 라운드 참가 실력이 정체되어있다. 예전엔 더 올라갈 수 있는데 운이 안 따라주는 느낌이었다면 지금은 느낌이 좀 다르다.... 재활이 꽤 오래 걸릴 것 같다. 1471A. Strange Partition 주어진 배열에서 인접한 두 원소를 대신해서 두 원소의 합으로 대체할 수 있다. 배열의 원소는 1개만큼 줄어든다. 이 연산을 원하는 만큼 한 후에, 배열의 각 원소를 x으로 나눈 값을 올림 하여 모두 더한 합의 최솟값과 최댓값을 구해야 한다. 최대인 경우는 연산을 한번도 하지 않은 원래의 배열에서 합을 구해주는 경우이고, 최소인 경우는 연산을 n-1번 적용한, 즉 배열의 원소가 1개만 남았을 때이다. [소스 코드] #include using namespace std; u.. PS를 위한 정수론 - (1) 에라토스테네스의 체 활용 기본적인 '에라토스테네스의 체' 개념을 아직 모른다면 wogud6792.tistory.com/46 글을 먼저 읽는 것을 추천한다. 크게 어렵지는 않다. 그렇다면 이제 이 에라토스테네스의 체를 활용하는 여러 가지 방법들을 알아보자. 1. 각 2부터 n까지의 자연수 k에 대해, "k가 갖는 가장 작은 소인수"를 계산하는 방법 이는 사실 매우 간단하다. 에라토스테네스의 체 원리를 생각해보면 현재 수가 아직 걸러지지 않았다면 소수이고, 현재 수의 배수들을 제거해나가는 방식이다. 이때, 제거되는 수는 합성수이고 제일 처음 제거될 때 이용되는 소수가 $k$가 갖는 가장 작은 소인수이다. int prime[1000001]; int main(void) { int N = 1000000; for (int i = 1; i Codeforces Round #690 (Div. 3) 풀이 A. Favorite Sequence 입력으로 문제의 그림과 같이 위치가 바뀐 수열이 들어온다. 다시 원래의 수열을 출력해주면 된다. (처음엔 바뀐 수열을 출력하라는 줄 알았다. 꽤나 비슷한 실수를 한 사람들이 많은 것 같다) #include using namespace std; int A[301]; int main(void) { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int T; cin >> T; while (T--) { int n; cin >> n; for (int i = 1; i > A[i]; for (int i = 1; i [BOJ 7812] 중앙 트리 [문제] www.acmicpc.net/problem/7812 7812번: 중앙 트리 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 트리의 정점의 수 n이 주어진다. (1 ≤ n ≤ 10,000) 각 정점은 0번부터 n-1번까지 번호가 붙여져 있다. 다음 n-1개 줄 www.acmicpc.net [난이도] - Platinum III (20.12.14 기준) [필요 개념] - Tree DP - DFS [풀이] 설명에서 나오는 S(u)는 'u를 루트로 하는 서브트리'를 뜻한다. 한 점에 대해서 다른 모든 점까지의 거리의 합을 구한다면 단순 Tree DP를 이용하여 노드의 개수만큼 탐색하면 된다. 하지만, 이 문제는 모든 정점에 대해서 고려를 해야하기 때문에 $O(n^2)$이고.. Atcoder Beginner Contest 185 (ABC 185) 풀이 [문제 링크] atcoder.jp/contests/abc185 AtCoder Beginner Contest 185 - AtCoder AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp [풀이] A. ABC Preparation 각 점수별로 문제 수가 나와있고, 하나의 문제 set을 만들기 위해서는 점수별로 하나씩 문제가 필요하다. 따라서 네 정수 중 최솟값을 출력하면 된다. #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(n.. [BOJ 5670] 휴대폰 자판 [문제] www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net [난이도] - Platinum III (solved.ac 20.12.13 기준) [필요 개념] - 트라이 (Trie) [풀이] 자동 입력이 되는 순간은 현재 노드에서 끝나는 문자열이 없으면서, 자식 노드가 하나밖에 없는 경우이다. 따라서 트라이를 생성할 때 자식의 수를 저장해두고, 문자열을 탐색할 때 자식의 수가 둘 이상이거나, 현재 노드에서 끝나는 다른 문자열이 있고 자식의 수가 1이면 버튼을 눌러줘야 하.. [BOJ 2809] 아스키 거리 [문제] www.acmicpc.net/problem/2809 2809번: 아스키 거리 첫째 줄에 거리의 길이 N이 주어진다. 다음 줄에는 거리에 원래 적혀져있는 알파벳이 주어진다. 셋째 줄에는 묶음 타일의 종류의 개수 M이 주어진다. 다음 M개 줄에는 각 묶음 타일에 적혀져있는 www.acmicpc.net [난이도] - Platinum 2 (20.12.11 solved.ac 기준) [필요 개념] - 아호코라식 (Aho-corasick) [풀이] 아호코라식 문자열 판별 알고리즘의 응용문제이다. 타일과 일치하는 부분을 제외한 문자의 개수를 구하는 문제인데, 단순하게 아스키 거리의 각 위치(index) 별로 끝에 일치하는 타일들을 모두 고려한다면 시간 초과가 발생할 것 같다....? (정확하게는 모르겠다) 따.. [BOJ 10256] 돌연변이 [문제] www.acmicpc.net/problem/10256 10256번: 돌연변이 인간의 DNA 구조는 A, C, G, T로 이루어진 하나의 긴 문자열로 표현할 수 있다. 이때, 몇 몇 질병은 DNA 구조를 나타낸 문자열의 어떤 연속된 부분 문자열과 관련이 있다는 것이 밝혀져 있다. 만일 DNA www.acmicpc.net [난이도] - Platinum 3 (solved.ac 20.12.11 기준) [필요 개념] - 아호코라식 (Aho-corasick) [풀이] 마커(marker)의 돌연변이의 경우의 수는 최대 $m^2$이다. m이 100이하이므로 모든 돌연변이를 직접 다 만들어도 무리가 없다. 그리고, 만들어진 돌연변이들을 트라이에 넣어두고, DNA문자열을 탐색한다. 이때, 모든 돌연변이들의 길이가.. 이전 1 2 3 4 5 6 7 다음
