Don't give up!

1753번: 최단경로 (acmicpc.net) 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? 주어지는 것은 방향성이 있는 그래프이고 구해야 하는 것은 모든 정점으로의 최단 경로입니다. 시작 정점에서부터 시작하여 연결된 경로의 정점에 가중치를 갱신하는 다익스트라 알고리즘을 사용하고자 하였습니다. 코드 import java.io.*; import java.util.*; class Main { static int V, E, K, INF; static L..

1697번: 숨바꼭질 (acmicpc.net) 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? 현재 위치가 X일때 목표지점 K로 이동할 수 있는 방법은 X-1, X+1, X*2로 3가지이지만 만약 X가 K보다 큰 값을 가지고 있을 경우 X+1, X*2는 최단시간을 구하는 데 큰 도움이 되지 않습니다. BFS를 수행하고, 같은 위치에 반복 도달을 검사에서 제외함으로써 문제를 해결할 수 있다고 생각하였습니다. 코드 package com.boj; impo..

1106번: 호텔 (acmicpc.net) 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? 문제에서 유의깊게 보아야 할 부분은 '적어도 C명'이었습니다. 3원을 투자하여 5명을 얻을 수 있다면 적어도 1명을 늘리기 위해 필요한 금액도 3원이며, 적어도 3명을 늘리기 위해 필요한 금액도 3원입니다. 적어도 C명 늘리기 위해 필요한 금액의 최소값은 C부터 C+100명을 늘리기 위해 필요한 금액의 최소값으로 구할 수 있습니다. (주어진 조건에서 비용으로 얻을 수 있는 고객의 수..