본문 바로가기

Algorithm54

[백준 Gold 3] 1937 욕심쟁이 판다 - Java 문제링크 : https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 접근 과정 : DFS를 통해서, forest[i][j] 에서 판다가 출발하는 경우를 모두 조사. 다만 이미 한번 조사했던 칸은 dp[i][j]에 저장된 값을 사용하여 재탐색 비용을 줄임 즉, DFS+메모리제이션으로 문제를 접근 (배열 이름만 dp....) 방문체크가 필요없는 이유 : 판다는 현재칸보다 더 큰 값의 칸으로만 이동하기 때문에 다시 같은 칸을 방문하지 않는다!! .. 2021. 12. 23.
[백준 Silver 1] 1309 동물원 - Java 문제링크 : https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 접근 과정 : 2차원 배열(zoo[][])을 선언하고, 2칸 모두 사자가 없는 경우 / 왼쪽칸에 사자가 있는 경우 / 오른쪽칸에 사자가 있는 경우로 경우의 수를 더했다 즉, Bottom-Up 방식으로 DP를 구현하였다. 소스 코드 및 결과 : package BOJ; /* 동물원 */ import java.io.*; public class BOJ1309 { public static void main(String[] args) throws NumberFormatException, IOException { BufferedR.. 2021. 12. 23.
[백준 Gold 1] 2098 외판원 순회 - Java 문제링크 : https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 접근 과정 : 백준 10971 외판원순회2 문제의 코드를 리팩토링 시키는 방향으로 시도해보았다. 완전탐색으로 모든 경우를 탐색하면 시간초과!! 즉, 메모리제이션을 통해 이전에 체크한 부분을 재활용해야 한다. DP[][]을 만들어서 이를 관리 i 도시에 있고 j 비트에 포함된 도시를 탐색한 상황에서, 남은 도시를 모두 방문하는 최소비용 또한, 결국 .. 2021. 12. 22.
[백준 Silver 2] 10971 외판원 순회2 - Java 문제링크 : https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 접근 과정 : 한 도시에서 출발하여 모든 도시를 방문한 뒤, 출발 도시로 돌아왔을 때의 비용이 가장 적은 것을 출력하는 문제. 방문체크를 하면서 완전탐색을 하는 방법을 생각 도시의 수가 최대 10개이기에, 비용을 저장한 배열을 그냥 탐색하면서 다음 경로를 추적. 방문체크는 비트를 이용하여 판단 비용을 누적해가면서 경로를 추적하다가, 만약 이.. 2021. 12. 22.

티스토리툴바