백준 9205 - 맥주 마시면서 걸어가기

백준 9205 - 맥주 마시면서 걸어가기

https://www.acmicpc.net/problem/9205

★ 풀이

상근이가 집에서 페스티벌까지 맥주를 마시면서 갈 수 있는지 없는지 알아야 하는 문제이다. 문제에서 맥주를 1병 마시면 50m를 갈 수 있다고 했다. 집에서 맥주 1박스(20병)을 들고 출발하므로 집에서는 총 1000m를 갈 수 있는 것이다. 또 편의점에 들린다면 리필을 할 수 있으므로 또 편의점에서도 1000m를 갈 수 있다. 결국 집에서 출발하므로 집에서 페스티벌까지 (편의점 * 1000 + 1000)m 이내의 거리면 맥주를 마시면서 갈 수 있다는 것이다.

모든 좌표간의 거리를 구할 수 있는 플루이드 와샬 알고리즘을 활용해서 최적화를 통해 구해줄 수 있는데, 플루이드 와샬에 필요한 인접행렬을 만들때 각 좌표에서 1000m이상인 거리는 갈 수 없는 거리(맥주가 부족)이므로 INF로 설정해야한다. 그리고나서 플루이드 와샬로 최적화를 시켜주면 각 좌표에서 목적지에 갈 수 있는지 없는지(INF) 여부를 알 수 있고 또 갈 수 있다면 비용(거리) 또한 알 수 있는데 이때 그 비용이 (총 편의점의 수(n) * 1000 ) + 1000 보다 작아야지만 갈 수 있다.

★ 소스 코드

import java.io.*; import java.util.*; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static final int INF = Integer.MAX_VALUE / 2 - 1; public static void main(String[] args) throws IOException { int T = Integer.parseInt(br.readLine()); while(T-- > 0) { int n = Integer.parseInt(br.readLine()); int dist[][] = new int[n + 2][n + 2]; int p[][] = new int[n + 2][2]; for(int i = 0; i

"); }else { bw.write("sad

"); } } bw.flush(); } }

from http://sweet-smell.tistory.com/52 by ccl(A) rewrite - 2021-09-16 23:27:29