알고리즘 문제/CodeJam34 [CodeJam][2017] Bathroom Stalls - Qualification Round C 문제 : https://code.google.com/codejam/contest/3264486/dashboard#s=p2 N이 9라고 할 때를 예로 들어보자.파란색이 연속된 빈 자리(탐색 중인 자리들). 빨간 색이 이때 선택되는 최적의 자리이다.연속된 빈 자리가 많을 수록 우선으로 선택된다. (최대, 최소가 크므로)그리고 연속된 빈 자리수가 같다면 구하고자 하는 다른 상점 or 화장실과의 최대, 최소 거리는 같다. -> 한꺼번에 계산할 수 있다. map을 하나 만든다. key 값은 연속된 빈 자리이고 value는 연속된 빈 자리 수의 개수가 된다.key 값이 큰 것부터 탐색한다. (거리의 최대, 최소는 연속된 빈 자리 수에 비례하므로)탐색중인 map의 key값을 n, value를 cnt라 하자.cnt만큼.. 2019. 1. 27. [CodeJam][2017] Tidy Numbers - Qualification Round B 문제 : https://code.google.com/codejam/contest/dashboard?c=3264486#s=p1 let) 문자열 N = "441"문자열 N으로 (N[index], index)를 하나의 요소로 하는 배열을 만든다음 N[index] 기준으로 오름차순 정렬한다.이 배열을 앞에서부터 탐색하면서(let, 탐색 중인 인덱스 = i) index가 탐색 중인 인덱스 i와 다를때까지 정답 문자열에 N[i]를 차례대로 넣는다.index와 i 가 다른 경우는 N[i] 보다 작은 숫자가 이후에 나온다는걸 의미한다.위의 예시에서는 i가 0일 때, index는 2이다. N[i] = 4보다 작은 N[index] = 1이 이후에 나오기 때문이다. index와 i가 다를 때를 찾았으면 오름차순이 안될 때까.. 2019. 1. 22. [CodeJam][2017] Oversized Pancake Flipper - Qualification Round A 문제 : https://code.google.com/codejam/contest/3264486/dashboard 그리디로 풀었다.앞에서부터 탐색하면서 '-' 가 나오면 나온 위치부터 + K 인덱스 까지 문자열 S를 flip 한다.'-' 가 나왔는데 현재 인덱스 + K 가 문자열 S 범위에 속하지 않는다면 불가능한 경우이므로 IMPOSSIBLE을 출력한다.문자열을 모두 탐색했을 때 flip한 횟수가 정답이 된다. 소스코드 : https://gist.github.com/fpdjsns/0d201929d53ab19e6a8fe943a623f04d 2019. 1. 22. [CodeJam][2018] Saving The Universe Again - Qualification Round 문제 : https://codejam.withgoogle.com/2018/challenges/00000000000000cb/dashboard 가장 뒤에 있는 CS를 바꾸는게 가장 큰 점수 하락을 만들 수 있다.(damage, S 개수) 를 담는 map을 만든다.문자열 P를 돌면서 문자열의 총 데미지를 구하고 map을 세팅한다.만약 S 개수가 D 보다 크다면 아무리 많은 횟수로 바꾸더라도 D보다 작거나 같은 수를 만들 수 없다.왜냐하면 S가 최소 1 데미지가 될 수 있기 때문이다.최소 횟수를 구하려면 damage가 가장 큰 것부터 C와 바꿔나간다. 바꿔나가면서 총 데미지를 갱신한다. (총 데미지 = 총 데미지 - damage + damage/2)C와 한 번 바꾼다면 그 S 문자는 데미지가 반으로 감소한다... 2019. 1. 22. 이전 1 ··· 3 4 5 6 다음
