-

계단오르기 2579https://www.acmicpc.net/problem/2579 [문제 풀이] i번째 계단을 밟았을 때 최댓값은 두 경우 - i-2번째 계단 밟고 i번째 밟을 경우 - i-1번째 계단 밟고 i번째 밟을 경우중 최댓값을 고르면 답!!??이 아니라 틀린다!! 2번조건 "연속된 세 개의 계단을 밟으면 안된다"는 조건이 있기 때문이다! 자, 그러면 어떻게 풀어야 할까?일단 2차원 배열을 생성한다. i번째 계단을 밟았을 때 1) 1번 연속으로 밟은 경우 : dp[1][i] 2) 2번 연속으로 밟은 경우 : dp[2][i]두 경우로 나눌 수 있다! 이때, 1) i번째 계단을 1번 연속으로 밟기 위해서는 i-2번째 계단에서 2칸 이동하는 방법밖에 없으므로 dp[1][i] = max(dp[1][i-..

이친수 2193https://www.acmicpc.net/problem/2193 [문제 풀이]자리수 : n dp[i][0] : i자리 이친수 중 0으로 끝나는 이친수의 개수dp[i][1] : i자리 이친수 중 1로 끝나는 이친수의 개수 dp[i][0] = dp[i-1][0]+dp[i-1][1]dp[i][1] = dp[i-1][0] 답 : dp[n][0]+dp[n][1] 1234567891011121314151617181920212223import java.io.BufferedReader;import java.io.InputStreamReader; /* * 2193번 이친수 */public class Main{ static long d[][]; static int n; public static void m..

1로 만들기 1463https://www.acmicpc.net/problem/1463 [풀이방법]dp[i] = i를 1로 만드는 최소 연산 수 dp[i] = min(dp[i-1], dp[i/2], dp[i/3])+1 모든 연산을 마친 후 dp[i]를 출력하면 답! 123456789101112131415161718192021222324252627282930313233import java.util.Scanner;/* * X가 3으로 나누어 떨어지면, 3으로 나눔. * X가 2로 나누어 떨어지면, 2로 * 1을 뺀다. * 범위 : 1 2 -> 1이렇게 4번이 걸린다.