본문 바로가기

다익스트라5

[프로그래머스 Lv3] : 경주로 건설 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 죠르디가 경주로를 건설하는 데 필요한 최소 비용을 계산할 수 있도록 도와주자. 풀이 인접한 상하좌우로 움질일 수 있으며 직선 도로를 건설하는 데는 100원, 코너를 건설하는 데는 500원이 소요된다. 즉, 같은 방향으로 이동할 때는 도로만 건설하면 되니까 100원 다른 방향으로 이동할 때는 도로 + 코너를 건설해야하므로 600원의 비용이 발생한다. "방향"이 중요한 요소임을 알 수 있다.. 2022. 7. 14.

[BOJ] 13595 : Mania de Par 문제 링크 13595번: Mania de Par (acmicpc.net) 13595번: Mania de Par Patrícia é uma ótima desenvolvedora de software. No entanto, como quase toda pessoa brilhante, ela tem algumas manias estranhas, e uma delas é que tudo que ela faz tem que ser em número par. Muitas vezes essa mania não atrapalha, apesar de causar est www.acmicpc.net 해당 지점까지 주어진 조건에 맞도록 최단거리로 이동하는 다익스트라 문제. 문제 해석 영어가 아닌 라틴어(?)로 되어있어서 일.. 2022. 4. 27.

[BOJ] 5901 : Relocation 문제 링크 https://www.acmicpc.net/problem/5901 5901번: Relocation Input Details There are 5 towns, with towns 1, 2, and 3 having markets. There are 6 roads. Output Details FJ builds his farm in town 5. His daily schedule takes him through towns 5-1-2-3-2-1-5, for a total distance of 12. www.acmicpc.net 다익스트라를 활용하는 문제 문제 해석 문제를 그대로 해석한게 아니라 해석해서 정리한 것이다. 농부 존은 그의 일과동안에 최단 경로로 다니기 위해서 농장의 위치를 옮기려고한다. 존.. 2022. 4. 25.

[BOJ] 1800 : 인터넷 설치 문제 링크 https://www.acmicpc.net/problem/1800 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 1번과 N번 컴퓨터를 연결시키기 위해 필요한 비용중 최대값의 최소가 되도록하는 문제. 풀이 일단 1번과 N번 컴퓨터를 최대 효율로 연결시켜야 하므로 다익스트라 알고리즘을 사용해야하는 것을 알 수 있다. 그런데 기존 다익스트라는 비용이 계속해서 누적된다. 그리고 그 누적 비용이 가작 적게 들도록 N에 도달하는 것이 보통인데, 여기서는 비용들 중 가.. 2022. 4. 20.

[BOJ] 24888 : 노트 조각 문제 링크 24888번: 노트 조각 (acmicpc.net) 24888번: 노트 조각 첫째 줄에 정점의 개수 $N$, 간선의 개수 $M$이 공백을 사이에 두고 입력된다. ($2\leq N \leq 200\,000,\ N-1 \leq M \leq 200\,000$) 다음 $M$개의 줄에 $i$번째 간선이 연결하는 두 정점 $u_i, v_i$와 간선의 길이 $w_ www.acmicpc.net 숭고한 Division2 F번 문제. 풀이 jhnah917은 반드시 최단경로로 가기때문에 참가자 lobo_prix가 우승하기 위해서는 공동우승을 하는 수밖에 없다. 즉, 최단거리로 가는 경로 중에 모든 노트조각을 줍고 갈 수 있는 경로를 찾는 문제. 최단거리로 가는 경로가 여러개 존재하기 때문에 모든 경로를 돌아보는 수.. 2022. 3. 31.

이전 1 다음

티스토리툴바