본문 바로가기

알고리즘 문제/CodeJam34

[Codejam][2021][Round 1A] 1. Append Sort 문제 : https://codingcompetitions.withgoogle.com/codejam/round/000000000043585d/00000000007549e5 이전 숫자를 prev, 현재 탐색 중인 숫자를 now라 하자. now > prev가 되도록 숫자를 now뒤에 추가해야 한다. 만약 prev가 now보다 작다면 추가 digit 없이 조건을 만족하므로 다음 숫자를 탐색한다. prev의 자리수가 now 자리수보다 작다면 반드시 prev가 now보다 작으므로 이 경우에 속한다. ex) prev = 10, now = 8 prev와 now의 자리수가 동일하다면 now 뒤에 숫자 0을 추가한다. ex) prev = 10, now = 10 => 100 이 외의 경우는 prev의 자리수가 now 자리수.. 2022. 3. 1.
[Codejam][2021][QR] 2. Moons and Umbrellas 문제 : https://codingcompetitions.withgoogle.com/codejam/round/000000000043580a/00000000006d1145 X = CJ 비용, Y = JC 비용. S = C, J, ? 로 이루어진 문자열 S 문자열의 ? 문자에 C 혹은 J를 대체한다고 할 때, 지불해야 하는 최소 비용을 구해라. DP로 풀 수 있다. dp[0][i] = S[i]가 'C' 일 때, S[~i] 까지 최소 지불금액 dp[1][i] = S[i]가 'J' 일 때, S[~i] 까지 최소 지불금액 dp 배열은 초기 값은 만들 수 없음을 의미하는 INF 값으로 세팅한다. 그리고 S[0]이 'C' 혹은 '?'인 경우 dp[0][0] 을 0으로 갱신한다. 또한 S[0]이 'J' 혹은 '?'인 .. 2022. 1. 8.
[Codejam][2021][QR] 1. Reversort 문제 : https://codingcompetitions.withgoogle.com/codejam/round/000000000043580a/00000000006d0a5c 문제에서 제공해주는 수도코드대로 코드를 작성하면 된다. 0 ~ N-1 를 반복문으로 탐색하며 탐색 중인 반복변수를 i라 하자. 먼저 L[i~] 부분배열에서 최소 요소의 인덱스를 구하면 이 인덱스가 j가 된다. 정답 변수에 j - i + 1을 더한다. L[i~j]를 역순 나열한다. 시간복잡도는 O(N^2) 소스코드 : https://github.com/fpdjsns/Algorithm-python/blob/main/Algorithm/codejam/2020/QR/1.%20Reversort.py 2022. 1. 8.
[Kickstart][2021][Round A] 1. K-Goodness String 문제 : codingcompetitions.withgoogle.com/kickstart/round/0000000000436140/000000000068cca3 입력 문자열을 탐색하면서 S[i] != S[N-i+1] 인 문자의 개수(let, cnt)를 센다. K와 cnt의 차이가 정답이 된다. 시간복잡도는 O(N/2). 소스코드 : github.com/fpdjsns/Algorithm/blob/master/codejam/kickstart/2021/roundA/1.%20K-Goodness%20String.cpp 2021. 3. 28.
[Kickstart][2020][Round F] 2. Metal Harvest 문제 : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff48/00000000003f4b8b#problem 소행성에 로봇을 설치하여 탐사하려고 한다. 한 번에 하나의 로봇만 기동할 수 있으며 여러 로봇을 한 번에 기동할수는 없다. 로봇은 수확할 수 있는 시간과 관계없이 K배수 시간만큼 배치가 가능하며 연속배치만 가능하다. i 번째 로봇은 로봇이 가지는 고유 시간범위 [Si, Ei] 동안 수확이 가능하다. 이 기간은 서로 겹치지 않는다. 로봇 수 N, 배치가능 시간 K, 로봇들의 수확가능시간 배열 S, E가 주어질 때, 가능한 계속 수확하기 위해 로봇을 배치하는데 필요한 최소 로봇 배치 개수는 몇개인지 구하라. 각 로봇들의 수.. 2020. 12. 24.
[Kickstart][2020][Round F] 1. ATM Queue 문제 : codingcompetitions.withgoogle.com/kickstart/round/000000000019ff48/00000000003f4ed8 ATM기에 돈을 인출하기위해 사람들이 서있다. 사람들은 Ai 만큼의 돈을 인출하고 싶어한다. 한 번에 인출할 수 있는 돈의 최대는 X이다. 만약 한 번에 원하는 돈을 인출할 수 없다면 돈을 인출한 수 사람들이 서 있는 줄의 가장 뒤에 선다. 원하는 돈을 전부 인출했다면 줄에서 이탈한다. 사람들이 인출하고자 하는 비용 배열 A. 사람의 수 N, 최대 인출 가능 금액 X가 주어질 때, 줄에서 이탈하는 사람들의 순서를 구해라. i 번째 사람이 인출하고자 하는 총 금액이 Ai라 할 때, 줄에 총 몇번 서는지 먼저 구한다. 줄에 서는 총 횟수는 (Ai + .. 2020. 12. 22.