본문 바로가기

Codejam23

[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.
[CodeJam][2017][Round 1B] A. Steed 2: Cruise Control 문제 : https://code.google.com/codejam/contest/8294486/dashboard N개의 말 정보를 탐색하면서 도착지까지 가는데 드는 시간 중 최대 시간을 구한다.말이 도착지까지 가는데 드는 시간 = (D - K) / S정답은 D / 구한 최대 시간 이다. 자료형은 double로 해야 조건에 맞는다. 시간복잡도는 O(N). 소스코드 : https://gist.github.com/fpdjsns/bba7e68cc46d3f7e77500d0caecaa74c 2019. 2. 17.
[CodeJam][2017] Play the Dragon - Round1A ProblemC 문제 : https://code.google.com/codejam/contest/5304486/dashboard#s=p2&a=2 - IMPOSSIBLE내가 한 번에 knight를 죽일 수 없고 (첫 번째 턴에서 끝낼 수 없음)knight에게 2번 이하 맞으면 죽는 경우 (첫 번째 턴에서 지거나, 나는 계속 힐해야 함)-> 단, 2번 맞았을때 죽는 경우(& 첫번째 턴에 나이트 못죽임)는 첫 번째 턴에 버프나 디버프를 건다.버프를 걸었을 때 한 번 공격하면 나이트가 죽는 경우 이길 수 있다.디버프를 걸었을 때 2번 맞아도 안죽는 경우 내가 이길 수 있다. - knight 턴에서는 무조건 나를 때린다. (정해져 있는 조건)디버프를 쓰려면 무조건 초반에 몰아서 써야 이득이다. - 회복 횟수, 나이트 공격력, 디.. 2019. 2. 9.
[CodeJam][2017] Ratatouille - Round1A ProblemB 문제 : https://code.google.com/codejam/contest/5304486/dashboard#s=p1 그리디로 풀었다.6번 case로 예를 들어보자. 3 370 80 901260 1500 700800 1440 16001700 1620 900cs 입력으로 받은 Q배열을 재료별로 오름차순 정렬한다. 700 1260 1500800 1440 1600900 1620 1700cs 이제 각 재료를 cnt 개 사용해서 만들 수 있는 패키지를 구한다.cnt는 1부터 시작한다.각 재료의 그램 수는 처음 입력에서 본 것과 같이 각각 70, 80, 90 이다. 먼저 각 재료들 하나로 만들 수 있는 패키지(Q)는 없다.하나인 경우 -> [63~77, 72~88, 81~99]. 만들 수 있는 패키지가 있을 때.. 2019. 2. 8.

티스토리툴바