https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 이 문제는 DP 또는 Greedy로 풀 수 있는데, DP 연습을 하고 있기 때문에 DP로 풀어봤다! 우선, 차분히 예제를 두고 쭉 적어봤다. 규칙을 찾아야 하기 때문! - 3의 배수 - 5의 배수 - 3와 5의 합으로 나올 수 있는 수 그런데 쭉 숫자들을 적어 내리다 보니, 8(3+5) 이후로는 3과 5로 모두 나타낼 수 있었다! 그래서, 초기값을 3, 5, 6으로만 주고 8 이후로 작은 문제의 답으로 큰 ..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 다익스트라는 시작점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘 플로이드-워셜은 모든 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘 모든 노드 간의 최단 거리를 구해야 하므로 2차원 인접 행렬 여러 라운드로 구성된다. 각 경로에서 새로운 중간 노드로 사용할 수 있는 노드를 선택하고 더 짧은 길이를 선택해 줄이는 과정반복 구현 각 라운드 별 각 노드별 모든 거리 살피면서 라운드..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net dp[i]에 i번째의 앞에서부터 원소까지의 증가 부분 수열의 원소 횟수(길이)가 담긴다 모두 최소 길이가 1이므로 dp에 넣어주면서 진행하고, 앞에 원소들을 확인하면서 진행. 앞에 원소가 나보다 작으면 증가 부분 수열에 들어가므로 그 원소의 dp 값 + 1 그런데, 여기서 시작점이 매번 다르므로 max로 dp[i]와 최..

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 너무 어렵게 생각해서 오히려 문제였던 DP 문제! dp[i]에 올 수 있는 가장 큰 수(합)를 구하면 된다. 여기서 증가 부분 수열은 연속되지 않아도 된다는 사실을 기억해야 한다. 각자 자기 위치에 올 수 있는 가장 큰 수를 구하면 되는데, 이를 위해서 앞에서부터 자신이 가질 수 있는 최댓값을 구하면 된다. 앞에 있는 애들을 쭉 보면서 나..

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 길이가 N인 오르막수의 개수를 구하는 문제 -> 길이가 1~N인 오르막수의 개수를 모두 구해보자. 표를 만들어서 해보면 큼큼 굉장히 지저분하지만, 딱 알 수 있다. dp의 행 i는 1~N까지의 길이, 열은 j로 끝나는 수를 말한다. 즉, dp[i][j]는 i길이의 오르막 수 중에서 j로 끝나는 수의 개수 여기서 관건은 사실 i, j를 선언하는 것이다. j를 개념..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net DP는 그 안에서도 굉장히 많은 유형이 있다고 생각한다. 이 문제는 DP 기본 문제 중 하나라고 생각하는데, 조건이 추가된 것도 그렇고, 작은 문제에서 큰 문제로 가는 방식도 그렇고. 정말.. 어렵다~ DP 우선 문제를 정리해 보자면, N번째 계단에 최댓값으로 올라가야 한다. 이동 방법은 1) 1칸 이동 2) 2칸 이동 중요한 게 바로 조건! 연속 3칸을 밟으면 안 된다. DP는 N보다 작은 애들의 결과로 N..