알고리즘 문제408 [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. [BOJ][1504] 특정한 최단 경로 문제 : https://www.acmicpc.net/problem/1504 최단거리를 구하는 문제이다.플로이드 알고리즘으로 먼저 모든 정점 간의 최단 거리를 구한다.1 -> N 까지 이동하는데 반드시 지나야 하는 지점 2개가 a, b라면나올 수 있는 경로는 1 -> ... -> a -> ... -> b -> ... -> N1 -> ... -> b -> ... -> a -> ... -> N위 경로 2개이다. 따라서 1 -> a 최단 거리 + a -> b 최단거리 + b -> N 최단거리1 -> b 최단 거리 + b -> a 최단거리 + a -> N 최단거리위 2개 중 짧은 거리가 정답이 된다.만약 구한 짧은 거리가 무한대라면 불가능한 경우이므로 -1을 출력한다. 소스코드 : https://gist.gith.. 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. [BOJ][1516] 게임 개발 문제 : https://www.acmicpc.net/problem/1516 전형적인 위상정렬 문제.입력값들로 위상 정렬을 위한 그래프를 먼저 만든다.건물의 cost 정보를 배열에 따로 저장해둔다. 큐를 하나 만들어서 우선시 개발되어야 하는 건물들이 없는 건물 인덱스를 모두 넣는다.큐에 들어갈 때 각 건물이 완성되기까지 걸리는 최소 시간이 정해진다.처음 큐에 값을 세팅할 때는 자기 자신이 만들어지는데 걸리는 시간이 각 건물이 완성되기까지 걸리는 최소 시간이 된다. 큐를 pop하면서 가져온 인덱스 건물(A)과 앞서 만든 그래프에서 간선을 가지고 있는 건물(B)에서 해당 간선 (A -> B)을 제거한다.간선이 있다는 뜻은 B 건물을 만드는데 A 건물이 우선시되어 만들어져야 한다는 의미이다.따라서 B 건물을 만.. 2019. 1. 20. 이전 1 ··· 59 60 61 62 63 64 65 ··· 68 다음
