DP8 [백준 2011] 암호코드 www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net DP를 사용하는 문제이며 리트코드에서도 유사한 문제를 푼 경험이 있다. DP[i]는 i번째 숫자를 포한해서 만들 수 있는 암호코드 최대 갯수로 정의한다. dp[i]에 영향을 주는 요소는 dp[i-1]과 dp[i-2]가 있다. 25114의 경우 2 -> B 25 -> B + E / ' ' +Y 251 -> BE + A / Y + A 2511 -> BEA + A / YA + A / BE + K / YA + K 25114 -> BEA.. 2020. 12. 15. [백준 1495] 기타리스트 www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net DP를 사용하는 문제이다. DP[I][J]를 가능한 최댓값으로 접근하면 문제를 풀 수 없다. 경우의 수가 많기 때문 따라서 DP[I][J]는 I번째 노래에서 J의 볼륨이 가능한지 여부여야 한다. DP[0][S] = 1로 초기화 된다. 그 다음에 입력을 받으면서 이전 노래에서 J 볼륨이 가능했다면 J +- IDX가 가능한지 확인하여 DP 배열에 체크한다. 마지막 노래에 볼륨 .. 2020. 12. 13. [leetcode 337] House Robber III The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night. Determine t.. 2020. 10. 20. [leetcode 32] Longest Valid Parentheses Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. 가장 긴 well formed parentheses 찾기 Example 1: Input: s = "(()" Output: 2 Explanation: The longest valid parentheses substring is "()". Example 2: Input: s = ")()())" Output: 4 Explanation: The longest valid parentheses substring is "()()". Example 3: Input: s = "" Out.. 2020. 10. 17. 이전 1 2 다음
