CS/Algorithm90 [알고리즘][DP][10844] 쉬운 단계 수 [알고리즘][DP][10844] 쉬운 단계 수 https://www.acmicpc.net/problem/10844 [풀이]n = 계단의 길이 k = 마지막 계단에 들어가는 숫자 ( 0 2018. 3. 24. [알고리즘][DP][11052] 붕어빵 판매하기 [알고리즘][DP][11052] 붕어빵 판매하기 https://www.acmicpc.net/problem/11052 [풀이]마찬가지로 가 가장 중요하다.Q[n-1] 과 Q[n]의 관계를 잘 보자!!!!!!!!!!!!!D[n] = n개를 팔아서 얻을 수 있는 최대 수익P[i] = i개로 이루어진 세트의 가격 이라 할 때,o + o + o + o + ... + o + i = n (세트의 갯수를 모두 더하면 n)마지막에 더한 i 세트의 가격 P[i]P[i]가 1 일 경우, D[n-1] 이 된다.P[i]가 2 일 경우, D[n-2] 가 된다....P[i]가 i 일 경우, D[n-i] 가 된다.이 때, D[n] = MAX(P[i] + D[n-i]) 라는 점화식을 도출할 수 있다. (이미 D[n-i]는 최대값이므로.. 2018. 3. 23. [알고리즘][DP][9095] 1, 2, 3 더하기 [알고리즘][DP][9095] 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095 [풀이]DP에서 가장 중요한 것은 점화식 찾기!경우의 수를 모두 구하려 하지말고 규칙을 찾아 반복해줘야 한다.당연한 것들을 이용해서 규칙을 찾자D[n] 은 1, 2, 3으로 이루어지는 방법의 수 ? + ? + ? + …… + ? + ? = n 라고 하자. n 이 되려면 3가지 방법이 있다.? + ? + ? + …… + ? + 1 = n 일 경우 ? + ? + ? + …… + ? = n-1 이다.? + ? + ? + …… + ? + 2 = n 일 경우 ? + ? + ? + …… + ? = n-2 이다.? + ? + ? + …… + ? + 3 = n 일 경우 ? + ? + ? + …… + ?.. 2018. 3. 22. [알고리즘][DP][11726] 2×n 타일링 [알고리즘][DP][11726] 2×n 타일링 https://www.acmicpc.net/problem/11726 [풀이]여기서 가장 중요한 것은 패턴을 알아내는 것이것을 식으로 나타냈을 때 D[num] = D[num-1] + D[num-2] D[0] = 1, D[1] = 1 [코드] 12345678910111213141516171819202122232425package algorithm_basic; import java.util.Scanner; public class q_11726 { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int num = scan.nextInt(); System.out.printl.. 2018. 3. 21. 이전 1 ··· 14 15 16 17 18 19 20 ··· 23 다음
