KickStart16 [Kickstart][2020][Round A] 2. Plates 문제 : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d40bb N개의 접시 스택이 주어지고, 각 접시들은 각 스택마다 K개의 접시들로 이루어진다. 각 접시들은 양의 정수를 가지고 있으며 접시들은 쌓여 있으므로 위에 있는 접시들부터 차례대로 가져올 수 있다. (중간에 있는 접시만 가져올수는 없다.) 최대 P개의 접시들로 저녁을 구성하려고 할 때, 해당 접시들의 양의 정수의 합이 최대가 되는 경우를 구하라. (최대 접시들의 고유 값의 합 리턴) 탐색은 dfs로 하고 메모이제이션을 위해 dp를 사용했다. n번째 접시 스택부터 N번빼 접시 스택까지 접시를 선택할 수 있다고 할 때, 총 P-p개의 접시로.. 2020. 3. 24. [Kickstart][2020][Round A] 1. Allocation 문제 : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d3f56 N 개의 집이 판매중이고, 각 집의 판매가격이 주어진다. 내가 B 달러를 가지고 있을 때, 최대 몇 채의 집까지 살 수 있는가? 구입할 수 있는 최대 개수의 집을 구하려면 가격이 작은 집들부터 구입하면 된다. -> 그리디 문제이다. 판매 가격을 오름차순 정렬한다. 앞에서부터 탐색하면서 B 달러로 탐색 중인 집을 구입할 수 있다면 정답 +1 을 해주고 B달러에 구입한 집 가격을 빼준다. 탐색 중인 집을 남은 달러로 구입할 수 있다면 판매 가격을 오름차순 정렬했기 때문에 이후에 나올 집들도 구매할 수 없을 것이다. 따라서 탐색을 종료하고.. 2020. 3. 23. [Kickstart][2019]2. Mural 문제 : https://codingcompetitions.withgoogle.com/kickstart/round/0000000000051060/0000000000058b89 부분합으로 풀었다.벽은 가장자리부터 파괴되고 벽의 총 N개라고 했을 때 최대 (N+1)/2 개의 벽을 칠할 수 있다.즉, 문제를 간단하게 보면 연속되는 (N+1)/2개의 벽을 선택할 때 구할 수 있는 최대 값을 구하는 문제이다.부분합 배열을 sum, (N+1)/2를 cnt라고 했을 때, sum[i] - sum[i-cnt]가 (N+1)/2개의 벽을 선택했을 때의 가치이고. i 범위가 [cnt, N] 일 때 구한 가치 중 최대 값이 정답이 된다.시간 복잡도는 O(N). 소스코드 : https://gist.github.com/fpdjsns.. 2019. 2. 25. [Kickstart][2019]1. Number Guessing 문제 : https://codingcompetitions.withgoogle.com/kickstart/round/0000000000051060/00000000000588f4 이진탐색으로 풀었다.정답이 될 수 있는 범위의 가장 최소, 최대 값을 가지고 그 중간 값이 정답이 될 수 있는지 확인한다.정답이 될 수 있는 경우 종료하고, 중간 값보다 정답이 작다고 한다면 범위는 최소 ~ 중간 값 -1이 되므로 최대 값을 중간 값 -1 로 갱신한다.중간 값보다 정답이 크다고 한다면 범위는 중간 값 + 1 ~ 최대가 되므로 최소 값을 중간 값 + 1 로 갱신한다.이를 정답을 구할 때까지 혹은 N번 반복한다. 소스코드 : https://gist.github.com/fpdjsns/c129fea086f319e7340126.. 2019. 2. 25. 이전 1 2 3 다음