본문 바로가기

알고리즘 문제/CodeJam34

[Kickstart][2020][Round A] 3. Workout 문제 : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d3f5b Tambourine 씨는 N개의 휘트니스 프로그램 세션을 준비했다. i번째 세션은 M[i] 분 동안 진행될 것이다. 진행 시간은 반드시 증가한다. (M[i] < M[j], i < j) 휘트니스 프로그램의 난이도는 연속되는 세션의 진행시간 차이들 중 최대값이다. 그녀는 난이도를 낮추기 위해 최대 K개의 추가 세션을 추가하고자 한다. 이 때, 추가 세션들도 진행 시간은 반드시 증가해야한다. 기존 세션들에서 최대 K개의 세션을 추가한다고 할 때, 가능한 난이도의 최소값은 어떻게 되는가? 이분탐색 문제이다. 구하고자 하는 값이 난이도의 최소.. 2020. 3. 25.
[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.
[CodeJam][2017][Round 1C] A. Ample Syrup 문제 : https://code.google.com/codejam/contest/3274486/dashboard#s=p0&a=0 그리디로 풀었다.학창 시절 때의 수학시간을 생각해보면 소스가 뿌려진 총 면적에서 높이는 각 팬케이크의 높이를 다 더한 값이지만 원의 너비는 가장 큰 팬케이크의 너비와 같다. 따라서, 너비를 기준으로 탐색한다. -> 너비를 기준으로 팬케이크를 오름차순 정렬한다.앞에서 부터 팬케이크를 탐색하면서 팬케이크의 높이를 구한다. K개를 만족한다면 현재 탐색중인 팬케이크의 너비 + 이때까지 구한 팬케이크 높이가 정답이 될 수 있는 경우이다. 현재 탐색중인 팬케이크의 너비는 너비를 기준으로 오름차순 정렬했으므로 이때까지 탐색한 팬케이크의 너비 중 최대값임을 보장한다. 또한 오름차순 정렬했으므.. 2019. 3. 7.
[CodeJam][2017][Round 1B] C. Pony Express 문제 : https://code.google.com/codejam/contest/8294486/dashboard#s=p2&a=1 참고 : http://kmjp.hatenablog.jp/entry/2017/04/24/1000 위 포스팅을 보고 풀었다. 입력N : 말을 가진 도시의 수Q : 흥미있어하는 정착지 개수N개의 Ei(i번째 말로 갈 수 있는 최대 거리. kilometers), Si(속도. k/s)NxN의 Dij(i -> j 거리)Q개의 Uk(시작 위치), Vk(종료 위치) 출력Q개의 Uk -> Vk로 가는 최소 시간. 플로이드 워셜 알고리즘을 2번 돌려서 풀었다.먼저 입력받은 D 배열(거리)로 i -> j로 가는 최단 거리를 플로이드를 돌려서 구한다. (O(N^3))D를 구했으면 D 배열을 탐색하면.. 2019. 3. 4.
[CodeJam][2017][Round 1B] B. Stable Neigh-bors 문제 : https://code.google.com/codejam/contest/8294486/dashboard#s=p1&a=1 우선은 R, Y, B만 있는 경우를 생각하자.이 때는 두 번에 나눠서 정답을 만들 수 있다.1회차에 R, Y, B를 순서대로 나열한다. (R+Y+B / 2의 오름차순 한 개수만큼만 넣는다. - 반)예를 들어, R 3개, Y 2개, B 1개라고 하면 먼저 3개를 나열한다. ex) RRR그리고 2회차에 만든 정답 문자열 사이사이에 알파벳을 다시 차례대로 넣는다. ex) RYRYRB알파벳 R, Y, B가 (R+Y+B)/2 보다 크다면 2회차 때 연속되게 나올 수 밖에 없기 때문에 정답이 불가능하다. -> IMPOSSIBLE 주의할 점은 R, Y, B를 순서대로 나열하면 안된다는 것이.. 2019. 3. 2.

티스토리툴바