CS/알고리즘7 백준 16236번 : 아기 상어[java] 1. 상어의 위치에서 bfs를 시작해 최단 거리에 있는 먹을 수 있는 물고기의 위치를 모두 저장해둡니다. → 모든 위치를 저장하는 이유는 하나의 최단거리를 발견하자마자 이동하면 가장 위쪽 우선, 가장 왼쪽 우선이라는 조건을 만족하지 않을 수 있기 때문에 모든 위치를 저장한 후 비교하여 이동할 위치를 결정합니다. 2. 다음으로 이동할 곳이 없거나 먹을 수 있는 물고기가 없을 때 까지 1번을 반복합니다. import java.io.InputStreamReader; import java.io.BufferedReader; import java.io.IOException; import java.util.LinkedList; import java.util.PriorityQueue; import java.util.Q.. 2023. 2. 13. 백준 1744번 : 수 묶기[java] 1. 1보다 큰 양수는 큰 수 부터 2개씩 짝을 지어 곱한다. → 곱하지 못하고 남은 양수는 더한다. 2. 1은 그대로 더하는데 사용한다. 3. 음수는 작은 수 부터 2개씩 짝을 지어 곱해서 양수로 만든다. → 곱하지 못하고 남은 음수는 0과 곱해서 0으로 만들거나 0이 없으면 그대로 더한다. import java.io.InputStreamReader; import java.io.BufferedReader; import java.io.IOException; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; public class Main{ public static void main(String[] a.. 2023. 2. 11. 백준 11066번 : 파일합치기[java] dp[i][j]는 i번 파일부터 j번 파일을 합치는데 든 최소비용이다. dp[i][i]는 chapter[i]이고, dp[i][i+1]은 chapter[i] + chapter[i+1] = sum[i] - sum[i-1]이다. dp[i][i+2]부턴 i과 i+1번을 합친 후 i+2번을 합치기, i+1번과 i+2번을 합친 후 i번을 합치기 중 선택해야 한다. 이를 식으로 나타내면, dp[i][i] + dp[i+1][i+2] + (sum[i+2] - sum[i-1]) 와 dp[i][i+1] + dp[i+2][i+2] + (sum[i+2] - sum[i-1]) 중 더 작은 수가 dp[i][i+2]이다. sum[i+2] - sum[i-1]은 현재 합치려는 파일 2개를 합치는데 사용하는데 드는 비용이다. 여기서 fr.. 2023. 2. 10. 이전 1 2 다음 반응형
