Alogorithm/DP

문제 링크: https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net ▶문제 세계적인 호텔인 형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다. 형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다. 예를 들어, “어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 정..

문제 링크: https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net ▶ 문제 2xn 직사각형안에 1x2와 2x1 타일을 채운다. ▶ 해설 DP 문제로 판단되어 점화식을 세웠다. 2 = 2 3 = 3 4 = 5 5 = 8 .... 9 = 55 위 처럼 나오므로 점화식은 DP[N]=DP[N-1]+DP[N-2]로 도출 할 수 있었다. import java.io.*; public class Main { public static void main(String[] args) thro..

문제 링크: https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 해당 문제를 처음에는 DFS로 시도했지만 시간초과로 실패했다. 그래서 DP로 다시 풀어 보았다. import java.math.BigInteger; import java.util.*; import java.io.*; public class Main { static int [] arr; static int t; ..

문제 링크: https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 그리디 알고리즘으로 가장 큰 제곱수를 빼고 나머지에서 가장 큰 수로 계속해서 나가는 형식으로 문제를 접근했지만, 당연히 틀렸다. DP로 풀어야 하는 문제였다. 밑에와 같이 개수=1일 때 가장 작고 그 후에 증가하고 줄어드는 추세를 볼 수 있다. dp[1] = 1^2 = 1개 dp[2] = 1^2 + 1^2 = 2개 dp[3] = 1^2 + 1^2 +..