All

풀이 더보기 여러 도시 여행 다닐 계획 최단 경로가 아닌 k번째 최단 경로를 구하기 원함 첫째 줄 n: 도시들의 갯수 m: 도시 간에 존재하는 도로의 수 k: k번째 최단경로 m개의 줄 a b c a도시 -> b도시 c시간 도시 번호는 1~n까지 연속하여 붙어있음 출력 n개 줄 출력, i번째줄에 1번 도시~ i번째 도시로 가는 k번째 최단 경로의 소요시간 출력 k번째 최단 경로가 존재하지 않으면 -1 최단 경로에 같은 정점 포함 가능(방문 체크x) i->i 1번째 최단 경로는 0 힌트 참조하면 i번 도시 k=1 k=2 1 0 -1 (이유: 2번째 최단 경로 없음) 2 2 (1 -> 2) 10 ( 1->5 -> 2) 3 6(1->2->3) 7(1->3) 4 4(1->2->4) 5(1->4) 5 6(1->5..

북서풍 다국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 6705 2274 1448 33.816% 문제 강한 북서풍이 불고 있다. 이 뜻은 동쪽과 남쪽 사이의 모든 방향으로 항해할 수 있다는 뜻이다. 북쪽이나 서쪽으로 항해하는 것은 불가능하다. 작은 섬이 여러 개 있는 바다가 있다. 섬은 좌표 평면의 한 점으로 나타낼 수 있다. y 좌표가 증가하는 방향은 북쪽, x좌표가 증가하는 방향은 동쪽이다. 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 섬의 수 n (1 ≤ n ≤ 75000)이 주어진다. 다음 n개 줄에는 각 섬의 좌표 xi, yi가 주어진다. 두 섬의 좌표가 같..

가운데를 말해요 시간 제한메모리 제한제출정답맞힌 사람정답 비율 0.1 초 (하단 참고) 128 MB 54527 15939 11943 30.373% 문제 백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다. 예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에는 백준이가 외치는 정수의..

알고스팟 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 (추가 시간 없음) 128 MB 35652 15383 10502 42.139% 문제 알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다. 알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 ..

알약 다국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 6520 4207 3252 66.941% 문제 70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다. 첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다. 다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다. 종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종..

1. 가중치가 별도로 주어져있다 - No: BFS, DFS로 풀이. but, dfs보다는 bfs를 더 선호. 이유: 보통 bad일경우 dfs, bfs 전부 같지만 일반적인 good 상황에서는 bfs 단계에서 끝나는 경우가 많음. DFS 일반적으로 표기는 다음과 같이 진행된다. 순회 과정(stack 방식 활용) A와 연결된 Node는 b와 c b와 c 중 선택해서 다음 level 선택 또 그다음 level 선택 반복 BFS (Queue 방식 활용) 같은 깊이에 해당하는 노드부터 탐색 A -> B -> C -> D -> E -> G -> F 순으로 가로로 체크 - YES: 다익스트라 알고리즘, 프림 알고리즘, 크루스칼 알고리즘 1. 다익스트라 알고리즘(정점 기반) (OElogv) 출발지를 선택하고 dista..

KCM Travel 시간 제한메모리 제한제출정답맞힌 사람정답 비율 3 초 256 MB 25033 1179 727 12.127% 문제 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세에 힘입어 구글 역시 대기업답게 비용 감축에 열을 내고 있었던 것이다. 초대장 내용에 의하면 구글은 찬민에게 최대 M원까지의 비용만을 여행비로써 부담해주겠다고 한다. 인천에서 LA행 직항 한 번 끊어주는게 그렇게 힘드냐고 따지고도 싶었지만, 다가올 결승 대회를 생각하면 대회 외적인 곳에 마음을 쓰고 싶지 않은 것 또한 사실이었다. 그래서 찬민은 인천에서 LA까..

웜홀 다국어 한국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 40884 9535 5928 21.838% 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다. 시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경..

네트워크 복구 스페셜 저지 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 192 MB 6071 3104 2162 49.667% 문제 N(1 ≤ N ≤ 1,000)개의 컴퓨터로 구성된 네트워크가 있다. 이들 중 몇 개의 컴퓨터들은 서로 네트워크 연결이 되어 있어 서로 다른 두 컴퓨터 간 통신이 가능하도록 되어 있다. 통신을 할 때에는 서로 직접 연결되어 있는 회선을 이용할 수도 있으며, 회선과 다른 컴퓨터를 거쳐서 통신을 할 수도 있다. 각 컴퓨터들과 회선은 그 성능이 차이가 날 수 있다. 따라서 각각의 직접 연결되어 있는 회선을 이용해서 통신을 하는데 걸리는 시간이 서로 다를 수 있다. 심지어는 직접 연결되어 있는 회선이 오히려 더 느려서, 다른 컴퓨터를 통해서 통신을 하는 것이 더 유리할 수도 ..

달리기 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 8823 3722 2497 45.817% 문제 KOI 장거리 달리기 대회가 진행되어 모든 선수가 반환점을 넘었다. 각 선수의 입장에서 자기보다 앞에 달리고 있는 선수들 중 평소 실력이 자기보다 좋은 선수를 남은 거리 동안 앞지르는 것은 불가능하다. 반대로, 평소 실력이 자기보다 좋지 않은 선수가 앞에 달리고 있으면 남은 거리 동안 앞지르는 것이 가능하다. 이러한 가정 하에서 각 선수는 자신이 앞으로 얻을 수 있는 최선의 등수를 알 수 있다. 각 선수의 평소 실력은 정수로 주어지는데 더 큰 값이 더 좋은 실력을 의미한다. 현재 달리고 있는 선수를 앞에서 부터 표시했을 때 평소 실력이 각각 2, 8, 10, 7, 1, 9, 4, 15라..