본문 바로가기

KickStart16

[Kickstart][2020][Round B] 3. Robot Path Decoding 문제 : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc8/00000000002d83dc (1, 1) 좌표에서 시작해서 109개의 행, 열이 있는 좌표가 있다. (w, h)는 w번째 열, h 번째 행을 의미한다. 이동하는 방법이 문자열로 주어진다. WEST는 방향을 의미한다. (W: West, E: East, S : South, N: North) X(Y) 형식으로도 표현하는데 X는 2~9인 숫자이고, Y는 이동하는 방법이 주어진다. X(Y)는 Y를 X번 반복하는 것을 의미한다. 예를 들어, 2(S2(E))는 SEESEESEE와 같다. 이동이 끝난후 w, h를 구해라. 가능한 숫자가 2~9 이기 때문에 숫자가 나오는 경우 .. 2020. 4. 25.
[Kickstart][2020][Round B] 2. Bus Routes 문제 : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc8/00000000002d83bf n개의 버스노선을 이용하여 여행을 하고 싶다. 버스노선을 차례대로 이용한다고 했을 때 (i < j, Xi 이용 후 Xj 이용) D 일 이내에 여행을 마쳐야 한다(마지막 버스를 D일 이내에 타야한다). i번 노선의 배차 간격이 주어졌을 때, (예를 들어 Xi = 2라면, i번째 버스는 2, 4, 6 ... 에 이용 가능하다.) 하루에 여러개의 버스 노선의 이용이 가능하다고 한다. 가능한 늦게 여행을 시작하고 싶을 때, D일 이내에 도착할 수 있는 여행 시작일을 구하라. D일까지 여행을 마치는 것이 가능하다. (버스 노선을 차례대로 이용.. 2020. 4. 23.
[Kickstart][2020][Round B] 1. Bike Tour 문제 : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc8/00000000002d82e6 산의 높이 배열이 주어질 때, 산의 peak의 수를 구하라. 자신의 높이보다 양쪽 산의 높이가 작을 때 peak가 된다. N을 산의 갯수라 할 때, 1~N-2 를 탐색하면서 arr[i-1] arr[i+1] 의 횟수를 구한다. 시간복잡도는 O(N). N = 산의 수. 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/codejam/kickstart/2020/roundB/1.%20Bike%20Tour.cpp 2020. 4. 20.
[Kickstart][2019][Round A] 1. Training 문제 : https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050e01/00000000000698d6 N명의 학생이 있고 이 중 P명의 학생을 선택하려고 한다. 각 학생들은 등급이 있는데 선택하는 학생들의 등급은 모두 같아야한다. 학생에게 1:1 코칭 1시간을 해주면 등급이 1증가한다. 최소의 시간으로 학생들의 등급을 높여 P명의 학생을 선택할 때, 코칭하는데 드는 시간의 최소값은 얼마인가. P명의 학생을 선택할 때, 이를 팀으로 이루기 위해 코칭하는데 드는 최소 시간은 얼마일까. P명의 학생들 중 가장 높은 등급을 학생들이 모두 가지게 된다면 팀을 이룰 수 있게된다. 즉, (가장 높은 등급 * P) - P명의 등급의 합이 코칭하는데.. 2020. 3. 27.
[Kickstart][2020][Round A] 4. Bundling 문제 : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d3ff3 Pip는 N개의 문자열을 가지고 있다. 문자열들은 모두 대문자로만 이루어진다. Pip는 이 문자열들을 그룹화 시키려고 한다. 이 때, 각 그룹은 정확히 K개의 문자열들로 이루어진다. 각 그룹의 점수는 그룹에 속한 문자열들의 공통 prefix 길이다. 만들 수 있는 그룹들의 점수의 합의 최대값은 얼마인가. 문자열 배열, 공통된 Prefix.. 트라이를 써야될 것 같은 느낌이 든다. 일단 N개의 문자열들로 Trie를 만든다. 그룹들의 최대값을 만드려면 어떻게 해야하는지 먼저 고민해보자. 최대값을 만드려면 prefix가 커야한다. 즉, 트.. 2020. 3. 26.
[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.

티스토리툴바