Coding Test

2579 - 계단 오르기https://www.acmicpc.net/problem/2579문제1. 한 번에 한 계단씩 or 두 계단씩 오를 수 있음-> 한 계단 밟으면서 이어서 다음 계단 or 다음 다음 계단2. 연속된 세 개의 계단 모두 밟아서는 X (시작점 계단에 포함 X)3. 마지막 도착 계단 반드시 밟아야 함=> 각 계단에 쓰여 있는 점수 주어질 때, 얻을 수 있는 총 점수의 최댓값?입력첫째 줄: 계단의 개수둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 순서대로 각 계단에 쓰여 있는 점수 주어짐계단의 개수(자연수) 출력: 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값풀이`int[] arr = new int[n + 1]`: 계단 점수`int[] dp = new int[n + 1]`: i번째 계..

9095 - 1, 2, 3 더하기https://www.acmicpc.net/problem/9095문제정수 4 -> 1, 2, 3의 합으로 나타내는 방법: 7가지 (합을 나타낼 때는 수 1개 이상 사용)1 + 1 + 1 + 11 + 1 + 21 + 2 + 12 + 1 + 12 + 21 + 33 + 1=> 정수 n이 주어졌을 때 n을 1, 2, 3의 합으로 나타내는 방법의 수입력첫째 줄: 테스트 케이스 개수 T0 출력각 테스트 케이스마다 n을 1, 2, 3의 합으로 나타내는 방법의 수풀이`dp[i]`: 정수 i를 1, 2, 3의 합으로 만드는 경우의 수`dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]` => 예시 참고 dp[1] = 1 1dp[2] = 2 1 + 1 / 2dp[3]..

1463 - 1로 만들기https://www.acmicpc.net/problem/1463 문제1. 3으로 나누어 떨어짐 -> /32. 2로 나누어 떨어짐 -> /23. -1 => 정수 N이 주어졌을 때, 연산 세 개 적절히 사용해서 1을 만들려고 함-> 연산을 사용하는 횟수의 최솟값입력: $10^6$ >= 자연수 N >= 1출력: 연산을 하는 횟수의 쵯솟값풀이`dp[i]`: 숫자 i -> 1로 만들기 위한 최소 연산 횟수dp[0] = dp[1] = 0=> 항상 가능한 경우: i - 1 -> 1 i - 1까지 최소 연산 횟수 구해져 있음 -> + 해서 i까지 도달하는 데 필요한 연산 수 계산 나눠떨어질 때 더 짧은 경로 O -> 최소 연산 횟수로 덮어씀`dp[i] = dp[i / 2] + 1`, `dp[i..