pseong

Problem - E - Codeforces codeforces.com 보자마자 트리디피 인 것은 알았지만 한 가지 착각한 것 때문에 시간이 너무 오래 걸렸다. dp[i] : i를 루트로 하는 서브트리 내에서 정답 이라고 했을 때 dp[i] 는 max(모든 자식 dp[j] 를 더한 값, max(dp[j]) + 1)이라고 생각했다. 여기서 간과한 사실은 이렇게 구현하면 max(dp[j]) + 1)에 포함된 노드들 중에 모든 자식 dp[k]를 더한 값이 존재할 수 있다는 것이다. max(dp[j]) + 1로 구한 값은 항상 그 자식들도 max(dp[k]) + 1로 구해져야 한다. 생각해 보면 max(dp[j]) + 1이라는 값은 트리의 깊이이다. 따라서 트리의 깊이와 모든 자식 dp[j] 를 더한 값은 분리..

Problem - F - Codeforces codeforces.com F번 치곤 쉽게 나와서 진짜 오랜만에 F번을 풀어봤다. 가장 안좋은 방법은 k개를 선택하고 k개를 차례대로 순회하면서 답을 구하는 방법이다. 이 방법은 O(nCk * k) 시간 복잡도 이므로 말도 안되는 시간이 걸린다.( 대략 30만 팩토리얼 ) k개를 선택하는 방법은 괸장히 비효율적이므로 다른 방법을 생각해 내야 한다. 답은 문제의 정의를 다르게 하면 된다. 디스크립션에서 k개를 선택하고 분할해서 계산한다. 우리는 분할 먼저 하고 k개를 선택할 것이다. ( 생각해 보면 이 풀이가 떠올리기 어렵지 않은 이유가, 연산의 순서를 바꾸는 방법은 흔한 풀이 방법중에 하나이기 때문일 것이다. ) 분할 먼저 하고 왼쪽에서 d개, 오른쪽에서 k-..

Problem - D - Codeforces codeforces.com 세로 x 가로 y 인 사각형으로부터 잘려 나온 n개의 조각들이 있다고 가정하자. (1) n개의 조각들로 세로 x 가로 y 인 사각형을 만들 수 있는지 판단할 수 있다. (2) 첫 번째 조각은 세로가 x이거나 가로가 y인 사각형 이어야 한다. 세로가 x인 조각과 가로가 y인 조각은 동시에 존재할 수 없다. 세로가 x인 조각을 먼저 잘랐다고 가정하면 가로는 y보다 작아지므로 가로가 y인 조각을 영원히 사용할 수 없다. 가로가 y인 조각을 먼저 잘랐다고 가정하면 세로는 x보다 작아지므로 세로가 x인 조각을 영원히 사용할 수 없다. 따라서 동시에 존재할 수 없으므로 항상 다음에 사용할 조각의 가로 또는 세로의 길이는 유일하다. 만약 가로가 ..

Problem - E - Codeforces codeforces.com Solution. 간선의 가중치가 k인 간선의 개수를 dp[k] 라 하자. 간선의 가중치는 연결된 두 노드의 최대 공약수 이므로 최대 공약수가 k가 되려면 두 수는 k의 배수가 되어야 한다. 따라서 k의 배수 중에서 2개를 선택하는 경우의 수 n/kC2를 구해주면 dp[k]의 초기값을 설정할 수 있다. 하지만 k의 배수 중에서 2k의 배수중에서 2개를 선택한 경우의 수는 최대공약수가 2k이므로 제외해 주어야 하고 마찬가지로 3k, 4k... 쭉 제외해 주어야 한다. 따라서 n부터 1까지 반대로 dp[i]를 채워 주면 답을 구할 수 있다. k를 선택했을 때 최대 공약수가 k + 1 인 추가할 수 있는 간선의 개수는 dp[k + 1] 이..

Problem - E - Codeforces codeforces.com 먼저 x가 y를 이긴다라는 것을 x에서 y로 가는 간선이 존재한다고 하자. 그리고 어떤 그래프에서 다른 모든 노드로 갈 수 있는 노드를 후보라고 하자. Lemma 1. 토너먼트의 승자는 최소 한 명은 존재한다. (후보는 무조건 한 명 존재한다.) Proof. 먼저 n이 1 또는 2일 때를 생각해 보자. 1 또는 2일 때는 무조건 어떤 한 노드는 다른 모든 노드를 방문할 수 있다. 여기서 노드를 하나씩 추가해 보자. 지문에 나온 대로 완전 그래프여야 하기 때문에 노드 하나를 추가할 때마다 기존에 있던 모든 노드와 연결되어야 한다. 여기서 기존에 있던 노드 중에서 모든 노드를 방문할 수 있는 노드를 x라 하자. 새로 추가하는 노드를 y라..

A번은 문제를 처음에 잘못 읽어서 조금 헤멨다. L과 R이 자기 자신도 포함해서 불빛을 밝혀 주는 줄 알았는데 아니었다. 아무튼 문자열에 R 다음에 L이 나오면 0이고 RL 문자가 있으면 R의 위치고 그게 아니라면 -1이다. B번은 구성적 문제고 배열을 만드는 문제다. 짝수일 땐 -1 0 -1 0 반복해서 출력해 주면 되고 홀수일 땐 식 잘 세우면 답이 나온다. C번은 또 배열 문제인데 관찰이 생각보다 간단해서 순조롭게 풀었다. m번째 원소 포함 왼쪽 구간에서 어떻게 두 개로 자르던 m번이 포함된 조각이 음수가 되게 해야 한다. m번째 원소 다음부터 끝까지 구간에서는 구간을 어떻게 두 개로 자르던 m번째 다음 원소가 포함된 구간이 양수여야 한다. 이 사실을 알았으면 우선순위 큐를 써서 잘 구현하면 된다...

번은 코포에 자주 등장하는 배열 조작 문제였다. 그냥 가장 작은 것을 바꿔주면 된다는 생각에 우선순위 큐 풀이가 생각났고 그렇게 풀었더니 맞았다. 추 후 답지를 보니 좀 더 깔끔하게 푼 풀이가 있었지만 어차피 시간 복잡도는 똑같으니까 그냥 넘어가는 게 나을 것 같다. B번은 구성적 문제인데 주어진 수식을 만족하는 순열을 하나 찾아서 출력하는 문제였다. 정말 문제 그대로 주어진 수식대로 구성만 하면 되었다. C번은 5틀 하고 맞아서 250점이나 깎였다. 처음에는 굉장히 단순하게 생각해서 차이가 짝수인지 홀수인지만 판별해서 제출했는데 알고 보니 아니었다. 그래서 좀 더 생각해 보다가 공약수라는 것의 특징에 대해서 생각해 봤다. 공약수는 생각해 보면 두 수의 차이가 존재하고 두 수의 공약수는 항상 그 차이보다..

제곱수로 나누어 떨어지는 경우 이미 처리해 줬기 때문에 제곱수로 안 나누어 떨어지는 경우에 대해서만 포함 배제의 원리를 사용해야 한다. 제곱수로 나누어 떨어지는 경우는 전부 계산에서 제외해 주었기 때문에 어떤 수의 소인수들은 전부 한개만 가지고 있다. 먼저 x까지의 모든 숫자의 개수는 x개이다. 소수인수가 홀수개로 이루어져 있다면 빼주면 되고 짝수개로 이루어져 있다면 더해주면 된다. 1557번: 제곱 ㄴㄴ 어떤수 N이 1이 아닌 제곱수로 나누어지지 않을 때, 이 수를 제곱ㄴㄴ수라고 한다. 제곱수는 4, 9, 16, 25와 같은 것이고, 제곱ㄴㄴ수는 1, 2, 3, 5, 6, 7, 10, 11, 13, ...과 같은 수이다. K가 주어졌을 때, K www.acmicpc.net