dp

https://www.acmicpc.net/problem/3687문제분석성냥개비 갯수가 주어지면, 해당 성냥개비로 만들 수 있는 숫자 최대값/최소값을 구해야한다. Dynamic Programming을 활용해 문제를 해결해야 한다. 이번 문제에서는 index를 '성냥 갯수', 저장하는 값을 'index 성냥갯수로 만들 수 있는 최소값' 이다. 최대값은? 잘 보면, 최대값은 '자릿수'가 많은게 깡패다. 또한 모든 성냥개비를 다 써야하는 조건때문에 최대값에서 쓰이는 숫자는 7(성냥3개)과 1(성냥2개)밖에 없다. 따라서 홀수일 때 7을 1개만 쓰고, 짝수일 때 1만 써서 수를 나타내면 된다. Greedy로 해결된다. 성냥개비 갯수가 n개 주어져서 어떻게 배열 크기를 정해야 하나 할 수 있지만, 문제 조건을 읽..

https://www.acmicpc.net/problem/1106 문제분석DP의 핵심인 점화식을 찾는것이 너무 어려운 것 같다. 아직 DP문제에 익숙하지 않아서 인 것 같기도하고...이 문제는 dp배열의 index를 인원, 저장하는 값을 최소 비용 으로 세팅한 뒤, 하나하나 해 나가는 것 이다. 저번에 풀었던 냅색 문제와 동일한 줄 알았는데, 한가지 다른 점 이 있다. 바로 같은 도시에 홍보를 2번, 3번.. 정수배로 할 수 있다는 것이다. 따라서, for문을 순회할 때 도시->인원 순으로 순회하면서 진행해야 해를 구할 수 있다. 코드import java.util.*;import java.io.*;public class Main { public static void main(String[]args)..

참고 블로그 : https://hongjw1938.tistory.com/47특징Greedy와 매우 유사하다. 전 구간에 적용이 가능한 '부분 최적해'를 구해서, 이를 전 구간에 적용하는 방식은 유사하다. 하지만 몇가지 다른 점이 있다. 이에 대해 아래서 얘기해보자. DP 사용 이유멀리서 본다면 DP는 재귀와 굉장히 유사하다. 하지만 재귀의 단점을 보완한 방식이 DP이다.예를 들어서, f(n)=f(n-1)+f(n-2)라는 피보나치 수열 공식을 구현한다고 가정하자. 이를 재귀로 구현해서 실행할때를 보자.f(1000)을 구하려고 할 때, 내 코드는 과연 f(3)=f(1)+f(2)를 얼마나 반복하게 될까?f(1000)=f(999)+f(998)f(999)=f(998)+f(997)...단순히 f(5)=f(4)+f(..