목록백준/Dynamic Programming (32)
mojo's Blog
[백준 1699] 제곱수의 합
문제 링크 => 1699번: 제곱수의 합 (acmicpc.net) 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 자연수 N을 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구해야 하는 문제이다. 첫번째로 접근한 방법은 다음과 같다. d[1] = 1 / 1개 d[2] = d[1] + d[1] / 2개 d[3] = d[1] + d[1] + d[1] / 3개 d[4] = 4 / 1개 d[5] = d[4] + d[5-4] / 1 + 1 = 2..
[백준 2225] 합분해
문제 링크 => 2225번: 합분해 (acmicpc.net) 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 다이나믹 프로그래밍 문제이다. 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구해야 한다. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. => 이부분에서 dp 를 활용해야 한다는 것을 확인할 수 있다. 다음과 같은 시뮬레이션으로 dp를 유추해보도록 한다. n=20, k=1 인 경우 합이 20일 경우 => 20 / 1개 , dp[1][20] = 1 합이 19일 경우 => 19 / 1개 , dp[1][19] = 1 ... 합이 0일..
[백준 2240] 자두나무
문제 링크 => 2240번: 자두나무 (acmicpc.net) 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 3차원 배열 dp[x][y][z] 를 설정하였다. (x : 자두의 위치, y : 자두가 떨어지는 초 단위, z : 자두의 움직일 수 있는 횟수) 이때 주의깊게 볼 점은 z = 1 일때 움직이는 횟수를 0으로 보는것이 핵심이다. (0으로 볼 경우 배열의 index가 -1을 침범하는 경우가 발생하기 때문) 처음의 자두의 위치가 1이라고 주어질 때, 자두가 떨어질 위치가 1, 2일때의..
[백준 2293] 동전 1
문제 링크 => 2293번: 동전 1 (acmicpc.net) 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 다이나믹 프로그래밍 문제이다. 오름차순으로 정렬된 동전을 통해 k원을 만족하게 되도록 하는 동전들의 개수를 구하는 문제이다. 예를들어서 동전 1원 하나만 들어왔다고 가정하자. 1 2 3 4 5 6 7 8 9 10(k) 1 1 1 1 1 1 1 1 1 1 1 이때 1원 이후로 값이 전부 채워진것을 확인할 수 있다. dp[1] = dp[1] + dp[0] (이때 dp[0] = 1 이라고 설정) = 0 + ..
[백준 14002] 가장 긴 증가하는 부분 수열 4
문제 링크 => 14002번: 가장 긴 증가하는 부분 수열 4 (acmicpc.net) 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 다이나믹 프로그래밍 문제 + 약간의 생각을 더 해서 풀어야하는 문제이다. 참고로 이문제는 N=1000 밖에 안되기 때문에, 이분탐색을 사용하지 않고 다이나믹 프로그래밍으로 해결이 가능하다. 그러나 문제는 가장 긴 증가하는 부분 수열을 특정지어서 값을 표현하는게 생각보다 쉽지는 않았던거 같다. 이 ..
[백준 11055] 가장 큰 증가 부분 수열
문제 링크 => 11055번: 가장 큰 증가 부분 수열 (acmicpc.net) 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 이 문제는 가장 긴 감소하는 부분 수열에서 증가로 변경되고 길이가 아닌 누적된 합을 구하는 문제이다. 그래서 dp 값을 길이가 아닌 누적합이 되도록 dp[j] + arr[i] > dp[i] 으로 변경만 해주면 그만이다. (이때 arr[j] < arr[i]인 경우에 고려해준다) 풀이 code #de..