본문 바로가기
728x90

다이나믹 프로그래밍35

[JAVA]백준 1937번: 욕심쟁이 판다 www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 1. 문제 설명 n*n 크기의 대나무 숲이 있을 때 판다가 어떤 지역에서 대나무를 먹는다. 그리고 그다음 지역은 현재 지역보다 대나무가 많이 있는 지역이어야 한다. 그렇지 않으면 판다는 죽는다고 할 때 판다의 최대한 오래 살 수 있는 일수를 구하는 문제이다. 2. 풀이 시작 위치가 정해져 있지 않기에 dfs로 곧장 푸는 것보다는 dfs+dp로 푸는 것이 효율적이다. 현재 위치에서 상, 하, 좌, 우 중.. 2021. 1. 28.
[JAVA]백준 2643번: 색종이 올려 놓기 www.acmicpc.net/problem/2643 2643번: 색종이 올려 놓기 첫 번째 줄에는 색종이의 장수가 주어진다. 다음 줄부터 각 줄에 색종이의 두 변의 길이가 주어진다. 두 변의 길이는 한 칸 띄어 주어진다. 색종이의 최대 장수는 100이고, 각 변의 길이는 1000보다 www.acmicpc.net 1. 문제 설명 색종이들의 가로, 세로 길이가 주어질 때 조건을 만족하면서 쌓을 수 있는 최대 색종이 장수를 구하는 문제이다. 조건 1. 새로 올려 놓는 색종이는 맨 위의 색종이보다 크지 않아야 한다. 조건 2. 새로 올려 놓는 색종이와 맨 위의 색종이의 변들은 서로 평행해야 한다. 2. 풀이 DP를 이용해서 풀 수 있는 문제이다. 색종이들의 길이들을 저장하고 그 길이들을 오름차순 정렬한다. 그 .. 2021. 1. 25.
[JAVA]백준 14002번: 가장 긴 증가하는 부분 수열 4 www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 1. 문제 설명 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하고 가장 긴 증가하는 부분수열의 길이와 가장 긴 증가하는 부분 수열을 출력하는 문제이다. 먼저 dp배열을 사용하여 현재 위치를 포함하여 만들 수 있는 가장 긴 증가하는 부분수열의 길이를 저장하였다. 그리고 cache 배열을 사용하여 현재 위치에서 가장 긴 .. 2021. 1. 20.
[JAVA]백준 1915번: 가장 큰 정사각형 www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 1. 문제 설명 0과 1로 된 n*m 배열이 있을 때 1로만 구성되어있는 가장 큰 정사각형의 크기를 구하는 문제이다. 현재 위치를 (X, Y)라고 할 때 현재 위치를 포함하고 만들 수 있는 가장 큰 정사각형의 길이를 cache 배열에 저장한다고 하자. cache [X][Y] 값은 cache [X-1][Y-1], cache [X-1][Y], cache [X][Y-1]의 최솟값의 1을 더한 값이다. cache [][] 값은 현재 위치에서 cache [][] 값만큼의 길이를 가진 정사각.. 2021. 1. 18.
728x90

티스토리툴바