반응형 Algorithm50 [DP] 백준 2193 이친수 (Pinary Number) BackJoon # 2193 - 이친수 (Pinary Number) https://www.acmicpc.net/problem/2193 대표적인 DP문제입니다. DP[N] 을 N개 자리수에 이친수를 만족하는 경우의 수라고 생각하겠습니다.N자리에 올 수 있는 숫자는 0 OR 1입니다. 각각에 경우에 대해서 생각해 보겠습니다. N자리에 0인 경우 N-1자리에 올 수 있는 숫자는 0 OR 1 둘 다 가능합니다. 따라서 DP[N] = DP[N-1] 이 성립합니다. N자리에 1인 경우 N-1자리에 올 수 있는 숫자는 0 만 가능합니다. 그렇다면 N-2 자리에 올 수 있는 숫자는? 0 OR 1 이 가능합니다. 따라서 . . . DP[N] = DP[N-2] 이 성립합니다. 이제 N자리에 0 이 올수도 1이 올수도 있으.. 2017. 10. 25. [DP] 백준 11057 오르막 수 (Ascending Number) BackJoon # 11057 - 오르막 수 (Ascending Number) https://www.acmicpc.net/problem/11057 대표적인 DP문제입니다. DP[N][L] 을 N자리수의 L이라는 숫자가 올 경우, 오르막 수 조건에 해당하는 경우의 수 라고 하겠습니다. DP[3][7] 이라고 하면 _ _ 7 을 뜻합니다. 그렇 다면 2번째 자리는 어떤 숫자가 올 수 있을까요?오르막 수 규칙에 의하면 0 ~ 7 이라는 숫자가 올 수 있습니다. 즉 N자리 L 숫자가 온다면, N-1자리 숫자는 0 ~ L 범위의 숫자가 올 수 있는 것입니다. 지금은 하나의 경우인 즉 L숫자를 가정했지만, 모든 경우의 수를 고려해야 하기 때문에 시그마로 식을 세워야 합니다. 결국 DP[N][L] = DP[N-1][.. 2017. 10. 24. [DP] 백준 2156 포도주 시식 (Wine Tasting) BackJoon # 2156 - 포도주 시식 (Wine Tasting) https://www.acmicpc.net/problem/2156 대표적인 DP문제입니다. 연속으로 3번 마시지 않으면서 주어진 N개 포도주를 어찌어찌 마신다면, 얼만큼 마실 수 있느냐 그 최고 값을 찾아라 입니다. 어찌어찌 마신다는 것은 우리가 어떻게 마셔라 라고 마음대로 정해줄 수 있다는 뜻입니다. 3번 연속으로 마실 수 없다는 것을 따져보면, 0번 연속 마실 수 있는 경우, 1번 연속 마실 수 있는 경우 , 2번 연속 마실 수 있는 경우가 있습니다. 자 그럼 점화식을 짜봅시다.ㅎㅎㅎㅎ dp[n] = 포도주 n개가 주어졌을 때, 가장 많이 마실 수 있는 양 p[n] = n번째 포도주의 양 0번 연속 마실 수 있는 경우 n번째 포도.. 2017. 10. 24. [GRAPH] 백준 5427 불(Fire) BackJoon # 5427- 불(Fire) https://www.acmicpc.net/problem/5427 package BackJoon; import java.awt.Point; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Fire { static ArrayList arrays; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); arrays = new ArrayList(); char [][]temp; fo.. 2017. 10. 21. 이전 1 ··· 7 8 9 10 11 12 13 다음 반응형
