전체 글62 백준 11053번 가장 긴 증가하는 부분 수열 주어진 수열에서 가장 길게 증가하는 부분 수열의 길이를 구하는 문제다. 수열에 주어진 각 숫자의 관점에서 최대 길이를 구해보면 다음과 같다. 1. 전체 수열이 A = {10} 으로 주어진 경우 최대 길이는 L = { 1} 이다. 2. 전체 수열이 A = {10, 20} 으로 주어진 경우 최대 길이는 L = { 1, 2} 이다. 3. 전체 수열이 A = {10, 20, 10} 으로 주어진 경우 최대 길이는 L = { 1, 2, 1} 이다. 4. 전체 수열이 A = {10, 20, 10, 30} 으로 주어진 경우 최대 길이는 L = { 1, 2, 1, 3} 이다. 5. 전체 수열이 A = {10, 20, 10, 30, 20} 으로 주어진 경우 최대 길이는 L = { 1, 2, 1, 3, 2} 이다. 6. 전.. 2023. 3. 15. 백준 2579번 계단 오르기 각각 점수가 부여된 계단을 규칙에 따라 올랐을 때 얻을 수 있는 총 점수의 최댓값을 구하는 문제다. 규칙은 다음과 같다. 계단은 한 번에 한 계단 또는 두 계단 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 마지막 계단은 반드시 밟아야 한다. 규칙 3을 기준으로 나머지 규칙을 적용하면 가능한 몇가지의 경우의 수를 얻을 수 있다. n-5 | n-4 | n-3 | n-2 | n-1 | n ^ - 마지막 계단을 반드시 밟아야 한다. ^ ^ ^ - 경우의 수 1. (n-3)계단과 (n-1)계단을 밟고 온다. ^ ^ - 경우의 수 2. (n-2)계단을 밟고 온다. - 경우의 수 1에 대해 N 번째 계단에서 얻을 수 있는 최대 점수(dp[N]) 는 N번째 계단의 점수와 직전 계단의 점수, 및 N-.. 2023. 3. 14. 백준 1003번 피보나치 함수 기존의 피보나치 함수 자체를 구현하는 문제와 달리, N번째 피보나치 수를 계산하기 위해 호출되는 0번째 피보나치 수(0)과 1번째 피보나치 수(1)의 호출 횟수를 구하는 문제다. N번 째 피보나치 수 fibonacci(0) 의 호출 횟수 fibonacci(1) 의 호출 횟수 0 1 0 1 0 1 2 1 1 3 1 2 4 2 3 5 3 5 6 5 8 7 8 13 8 13 21 N번 째 피보나치 수를 구하기 위해 fibonacci(0)와 fibonacci(1)이 호출되는 횟수를 나열하였다. 신기하게도 각 호출횟수도 역시 피보나치 수열을 구성하고 있었다. N번째 피보나치 숫자의 fibonacci(0) 호출 횟수를 fibonacci(N, 0) 이라고 한다면 다음과 같은 식을 작성할 수 있다. fibonacci(.. 2023. 3. 14. 백준 1010번 다리 놓기 조합으로 해결할 수 있는 문제다. 위와 같은 조합 공식에 따라 팩토리얼을 구현하여 문제를 풀이할 수도 있지만, 단순 계산으로 풀이한다면 계산량이 매우 클 것이다. 따라서 조합의 2가지 성질과 동적 프로그래밍을 활용하여 풀이하였다. import java.util.Scanner; public class Main { static int[][] dp = new int[30][30]; public static void main(String[] args) { Scanner in = new Scanner(System.in); StringBuilder sb = new StringBuilder(); int T = in.nextInt(); for (int i = 0; i < T; i++) { int N = in.nextI.. 2023. 3. 14. 이전 1 ··· 8 9 10 11 12 13 14 ··· 16 다음
