MathTrauma

문제 링크 : https://www.acmicpc.net/problem/14497 14497번: 주난의 난(難) 주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다. ‘쿵... 쿵...’ 주난이는 점프의 파 www.acmicpc.net 설명을 이해하는데 시간이 걸렸지만 대략 다음과 같이 해석하면 될 듯하다. 문제의 표현 '한 겹의 친구를 쓰러뜨린다.' 의 의미는 현재 0 인 칸만을 이용해서 도달할 수 있는 1 은 제거할 수 있다가 된다. (매 단계 도달한 1 은 제거하고 다음 단계로 진행한다.) 그렇다면 출발 지점(*)에서 도착 지점(#)에 이르는데 거치는 1 의 개수의 최소값 +1 을 구하는 문제가 된..

출발, 도착 지점과 대포들이 놓인 지점들을 정점으로 두고 각 정점들 사이의 이동시간을 가중치로 두면, 일반적인 최소 비용 문제(최단 경로 문제)가 된다. 대포를 이용해서 이동하거나 도보로 가거나 두 가지 선택지 있다. 위의 정보로부터 대포의 위치가 아닌 시작 정점을 제외한 정점에서 다른 정점을 잇는 간선의 가중치는 \[ time= \min( distance/5. \; , 2+|distance-50|/5.) \] 로 두면 된다. 시작 정점에서 다른 정점까지 가중치는 \[time = distance/5. \] 으로 둔다. (대포의 위치가 시작 위치와 겹쳐도 위의 식들은 유효하다. 0 시간을 이동해서 대포로 이동하는 상황이 될 것이다.) #include using namespace std; const doub..

문제 링크 : https://www.acmicpc.net/problem/16681 16681번: 등산 첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다. (2 ≤ www.acmicpc.net 문제에서 등산의 '가치' 를 (얻은 성취감) - (소모한 체력) 으로 계산 라 했는데 성취감은 중간 경로에 관계없이 도달한 지점의 높이에만 의존한다. 한편, 거리당 소모 체력을 D 라 했으니 소모한 총 체력 = D * (거리) 이므로 결국 각 지점까지의 '최단 거리' 를 구하는 문제로 환원된다. 각 지점까지 높이가 증가한 다음 높이가 감소한다는 식으로 생각하면 머리 아프다...

문제 링크 : https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 통상의 거리(비용)을 순서쌍 비용으로 바꾸면 된다. 즉, 거리를 pair(지나온 g의 개수, g 인접한 곳을 지난 횟수) 로 두면 평범한 최단 경로 문제가 된다. 하지만, 문제의 조건을 여러 번 잘못 읽었다. 시작, 마지막 지점은 쓰레기 옆이어도 count 하지 않는다는 조건도 한참 뒤에서야 봤다. #include using namespace std; s..

문제 링크 : https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 지원 비용의 크기가 크지 않아서 각 node(공항) 를 방문했을 때, 다른 비용으로 도달했으면 다른 node 처럼 생각하고 최단 경로를 찾으면 된다. '시간'과 '비용' 두 가지 값을 다루기 때문에 헷갈릴 수 있으니 변수명을 정리하자. 다익스트라 알고리즘을 사용하는데 이중 배열 Dst의 값은 시간이다. 즉, '시간'='거리' 로 처리한다. 거리(..