Algorithm22 백준 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. 백준 2231번 분해합 분해합은 어떤 자연수 N이 주어졌을 때, 생성자 숫자를 구하는 문제다. 반대로 분해합은 어떤 자연수 N과 N을 이루는 각 자리수의 합을 의미한다. 예를 들어 N = 245 라면 분해합은 245 + (2 + 4 + 5) = 256 이다. 이 문제는 숫자를 증가시키며 분해합을 계산하고, 그 계산값이 N과 일치하는 숫자를 출력해 풀이하였다. import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); int ans = func(N); System.out.println(.. 2023. 3. 13. 이전 1 2 3 4 5 6 다음
