Partially Committed

15681번: 트리와 쿼리 (acmicpc.net) 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 트리에서 DP 를 사용하는 입문 문제! 문제는 단순하다. Q 개의 쿼리가 들어오면 이에 따른 출력을 해주면 된다. 쿼리는 노드 V 에 대한 서브 트리를 구성하는 노드들의 개수를 반환하는 것이다. 입력 조건을 보면, 트리의 크기도 상당히 큰 편이기도 하지만, 쿼리가 최대 100,000 개가 들어올 수 있다. 노드 V 에 대한 서브 트리를 구성하는 노드 ..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 정수 n 을 1로 만들기 위한 연산 횟수의 최솟값을 dp[n] 이라고 가정하자. 그러면 dp[0] = dp[1] = 0, dp[2] = 1, dp[3] = 1 dp table 을 아래와 같이 bottom-up 방식으로 채워나갈 수 있다. 1. N 에 대하여 N-1 이 가능하다면 dp[n] = dp[n-1]+1 2. N 이 2로 나누어 떨어지면 dp[n] 은 dp[n/2]+1 와 dp[n-1]+1 중 더 작은 값을 선택 3. N 이 3으로 나누어 떨어지면 dp[n] 은 dp[n/3]+1 와 dp[n-1]+1 중 ..

시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 512 MB 285 124 98 47.573% 문제 신을 모시는 사당에는 신을 조각한 돌상 N개가 일렬로 놓여 있다. 각 돌상은 왼쪽 또는 오른쪽을 바라보고 서있다. 창영이는 연속한 몇 개의 돌상에 금칠을 하여 궁극의 깨달음을 얻고자 한다. 궁극의 깨달음을 얻기 위해서는 가능한 한 많은 금색 돌상들이 같은 방향을 바라보아야 한다. 방향이 다른 돌상은 깨달음에 치명적이다. 깨달음의 양은 아래와 같이 정의된다. | (왼쪽을 바라보는 금색 돌상의 개수) - (오른쪽을 바라보는 금색 돌상의 개수) | 창영이는 궁극의 깨달음을 얻을 수 있을까? 입력 첫째 줄에 돌상의 개수 N이 주어진다. 둘째 줄에 돌상이 나열된 순서대로, 각 돌상이 바라보고 있는 방향이 주어..

연속합 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 (추가 시간 없음) 128 MB 115866 41697 29399 34.685% 문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이..