원하는 것은 뭐든지

문제 풀이 예상 시간보다 지나가면 다른 해석을 보고 있습니다. 문제풀이문제 해석1. 현서는 찬홍이에게 택배 배달을 가야함2. 가는 길마다 소가 있어서 안전하게 지나가려면 여물을 줘야 함3. 현서는 최단거리로 가는거 보다 차라리 고생하고 여물을 조금 주는 것을 선택하고싶음4. 현서는 1번 찬홍이는 N에 있음5. 첫째줄에 N, M이 주어진다. N은 헛간, M은 길의 수6. 밑으로 M줄은 양방향 길을 소에게 줘야하는 여물의 수 까지 포함해서 주어짐 A(헛간) B(헛간) C(소여물)7. 1번 부터 N으로 갈 때 여물을 가장 적게 줄 수 있는 경우를 구해라!문제 풀이1. 기본적인 다익스트라 풀이로 쉽게 풀이가능2. 양 방향으로 길 담아준다.3. 우선순위 큐를 weight 기준으로 정렬한다.4. 초기값으로 출발 e..

문제 풀이 예상 시간보다 지나가면 다른 해석을 보고 있습니다. 문제풀이문제 해석1. N개의 도시가 있고 도시 간 이동하는 버스가 M개 있다.2. 버스는 출발도시, 도착도시, 시간으로 나타낼 수 있다.3. 도착하는 시간은 음수 일 수 있다. 시간 역행이 가능하다는 뜻4. 1번 도시에서 각 도시로 가는 가장 빠른 시간을 구하면 되는데 무한으로 과거로 갈 수 있는 경우 첫째 줄에 -1 출력5. 도시로 못가는 경우 -1 출력, 나머지는 시간 출력문제 풀이1. 가중치가 음수의 값이 존재한다. 벨만-포드 알고리즘을 사용한다.2. 벨만포드 알고리즘 내에서 거리 배열을 long으로 해주어야 한다.    - 최악의 경우 500*6000*-10000의 사이클을 돌아 -30억이 나올 수 있기 때문이다.    - 양의 경우에..

문제 풀이 예상 시간보다 지나가면 다른 해석을 보고 있습니다. 문제풀이문제 해석1. 세준이는 0에서 출발해서 목표지점까지 운전해서 가야 한다.2. 가는 길 중간마다 지름길이 존재한다.3. 역주행은 없기 때문에 도착지점이 시작지점보다 낮을 수는 없다.4. 가장 적게 운전하는 경우 거리를 적어라문제 풀이1. 다익스트라로 풀이2. 하지만 정형화된 다익스트라 풀이가 아니고 전체 길이에 대해서 해야 한다.3. 고속도로 전체를 노드라고 생각하고 graph와 dist 또한 고속도로 최대 길이까지 만들어줘야 한다. 그 이유는    - 출발지점과 도착지점이 가야 하는 곳 위일 수도 있다.4. 재귀를 사용해서 0부터 출발하여 도착지점까지 가면서 다익스트라를 실시한다.소스코드package online.judge.baekjo..

문제 풀이 예상 시간보다 지나가면 다른 해석을 보고 있습니다. 문제풀이문제 해석1. 짝수개의 주사위가 주어진다. 주사위는 1~n까지의 번호를 가지고 있고 정육면체 주사위고 각 면이 나올 확률은 같다.2. A는 먼저 주사위를 절반 가져갈 수 있다.3. 가져간 주사위를 모두 돌려서 나오는 값들의 합이 큰 사람이 이긴다.4. A는 먼저 주사위를 가져갈 수 있기 때문에 어떻게 가져가야 이길 수 있는지 주사위 번호를 1차원 배열로 오름차순 출력해라5. 각 주사위의 면의 원소는 1~100까지이다.문제 풀이1. 기업기출문제 답게 복합 알고리즘을 사용해야 한다.2. 주사위를 선택하는 과정을 백트래킹을 선택3. 그 후에 선택된 주사위(A)와 선택되지 않은 주사위(B)들의 합을 구하는 과정 DFS 선택4. 주사위 합 Li..