본문 바로가기

분류 전체보기

 (215)
백준 1005 ACM Craft (Java) 1. 문제 링크 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 건설 순서가 우선되는 것이 있어서 위상정렬을 한다. 위상 정렬을 하면서 큐에서 꺼낼 때 dp를 다. dp에 있는 값과 지금 온 값 중 더 큰 시간을 저장하면 문제에서 원하는 결과를 얻을 수 있다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.uti..
백준 17472 다리 만들기 2 (Java) 1. 문제 링크 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 bfs를 이용해 섬을 구분하여 각각 몇번째 섬인지 저장한다. 섬 사이 거리는 dfs를 이용해 다른 섬이 나올 때까지 한다. 그 거리 중 1이 아닌 최소 거리를 저장한다. 최소 스패닝 트리를 이용하여 모든 섬을 연결하는 최소 길를 구한다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.Inpu..
백준 14925 목장 건설하기 (Java) 1. 문제 링크 14925번: 목장 건설하기 랜드 씨는 퇴직금으로 땅을 사서 목장을 지으려 한다. 그가 사려고 소개받은 땅은 직사각형이고 대부분 들판이지만, 여기저기에 베기 어려운 나무와 치울 수 없는 바위가 있다. 그는 목장을 하 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 목장을 건설 가능한 좌표는 true로, 건설 불가능한 좌표는 false로 저장한다. 건설이 가능한 좌표가 나왔으면 해당위치에서 (-1, 0), (-1, -1), (0, -1)의 dp 중 최솟값을 선택하고 1을 더한 값으로 저장한다. 2-1. 앞의 3 좌표는 정사각형의 각 모서리로 포함되는 위치들에서 나왔다 2-2. 그 중 제일 작은 값만큼만 건설이 가능하고, 지금 자리도 건설이 되니까 1을 더했다. 좌표마다..
백준 2775 부녀회장이 될테야 (Java) 1. 문제 링크 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 dp 중 쉬운 편에 속하는 문제이다. 0층에 살고 있는 사람들을 먼저 저장한다. 그것들을 바탕으로 아래층에 살고 있는 사람의 수를 더한다인 줄 알았는데 테케를 보고 점화식을 수정했다. map[i][j] = map[i-1][j]+map[i][j-1] 한 층 아래에 살고 있는 사람과, 옆 집에 살고 있는 사람의 수를 더하면 답이 나온다. 4. 코드 import java.io.BufferedReader; import java.io.InputStream..
백준 21736 헌내기는 친구가 필요해 (Java) 1. 문제 링크 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 BFS를 이용하여 벽이 아닌 공간을 전부 방문한다. P가 나올 경우 결과값을 1씩 더한다. 갈 수 있는 공간을 전부 가면 끝낸다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import java.io.IOExceptio..
백준 17070 파이프 옮기기 1 1. 문제 링크 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 하나씩 움직여보는 풀이와 dp 풀이가 있다. 첫번째 방식은 메모리는 402,508KB, 시간은 880ms 가 나온다. 두번째 방식은 메모리는 11,564KB, 시간은 76ms가 나온다. 확실히 dp가 성능 면에서 우수하다. 4. 코드 1) 구현, 시뮬레이션 import java.io.BufferedReader; import java.io.IOException; import java...
백준 10971 외판원 순회2 (Java) 1. 문제 링크 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 외판원 순회 문제로 전형적인 TSP 문제이다. 가장 적은 비용으로 순회를 해야하기 때문에 순열로 방문할 도시의 순서를 정했다. 또한 순회라는 것이 첫 출발점으로 다시 돌아오는 것이기 때문에 시작점은 1번으로 잡고 했다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.I..
백준 1874 스택 수열 (Java) 1. 문제 링크 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 입력받은 값이 지금 들어간 값보다 크면 값을 스택에 넣는다. 그 후에 입력받은 값이 들어가있는 값과 같으면 스택에서 꺼낸다. 입력받은 값이 들어가있는 값보다 작으면 top에 있는 것을 꺼낸다. push와 pop을 반복하면서 해당 수열이 나오는지 확인하면 된다. 4. 코드 import java.io.BufferedReader;..

티스토리툴바