Solve Algorithms/DP, BruteForce
-
1915 : 가장 큰 정사각형Solve Algorithms/DP, BruteForce 2020. 5. 5. 14:09
출처 : https://www.acmicpc.net/problem/1915 알고리즘 분류 : 다이나믹프로그래밍 문제 n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오. 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 0 위와 같은 예제에서는 가운데의 2 × 2 배열이 가장 큰 정사각형이다. 입력 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. 출력 첫째 줄에 가장 큰 정사각형의 넓이를 출력한다. 접근 map[i][j]이 1일 때, map[i-1][j], map[i][j-1], map[i-1][j-1]이 모두 1이면, 정사각형을 이룬다. 처음에는 if문을 이용하여 1인지..
-
1965 : 상자넣기Solve Algorithms/DP, BruteForce 2020. 5. 5. 13:35
출처 : https://www.acmicpc.net/problem/1965 알고리즘 분류 : 다이나믹프로그래밍, LIS 문제 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다. 앞의 예에서 차례대로 크기가 1, 2, 3, 7인 상자를 선택하면 총 4개의 상자가 한 개의 상자에 들어가게 된다. 상자의 크기가 주..
-
1309 : 동물원Solve Algorithms/DP, BruteForce 2020. 5. 5. 13:14
출처 : https://www.acmicpc.net/problem/1309 문제 어떤 동물원에 가로로 두 칸 세로로 N칸인 아래와 같은 우리가 있다. 이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다. 동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다. 입력 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. 출력 첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라. 접근 i번째 ..
-
11054 : 가장 긴 바이토닉 부분 수열Solve Algorithms/DP, BruteForce 2020. 4. 30. 13:30
출처 : https://www.acmicpc.net/problem/11054 접근 dp1[i]는 i번째일 때 증가 수열의 길이이다. (i는 0부터 n까지 증가) dp2[i]는 i번째일 때 증가 수열의 길이이다. (i는 n부터 0까지 감소) ans = dp1[i] + dp2[i] 이라고 한다면, ans는 (i번 째 수를 바이토닉 수열 중 가장 큰 수로 했을 때의 수열의 길이)+1 이 저장된다. '+1'인 이유는 대칭성 때문. 따라서, 정답은 ans-1이다. dp1에 대한 for문을 살펴보자. list[i] > list[j] : 이전 값 보다 큰 값이어야, 증가 수열이 되므로. tmp < dp1[j] : tmp에는 dp[1]부터 dp[j-1]까지 값 중 최댓값이 들어있다. 따라서, 이를 만족하면, 새로운 최..