문제 탐색하기
입력 자료 정리
- n은 계단의 개수, 즉 입력값의 수다.
- 이후 들어오는 입력값들은 각 계단의 수다.
해결방법 추론
- 이 방법을 완전탐색으로 해결하려면 백트래킹으로 해결할 수 있을 것처럼 보인다
- 하지만 n의 최대 입력값이 10000이기 때문에 시간제한에 걸릴 것이고,
결국 다른 방법을 선택해야 했다 - 그래서 선택한 방법은 DP이다
- dp를 이용해서 지금까지의 계단 수의 합을 누적한다면,
시간제한에 걸리지 않고 문제를 해결할 수 있을 것이다!
시간복잡도 계산
- n만큼 순회하면서 dp의 값을 누적하기 때문에 연산은 n만큼 발생한다
- 즉 시간복잡도는 O(n)이고 시간제한에 걸리지 않는다!
점화식 추론
- 점화식은 어떻게 설계할 수 있을까 추론해보자
- 먼저 n이 1이라면 계단은 한개이고, 그 한칸의 수만이 얻을 수 있는 점수일 것이다
- 따라서 dp[1] = arr[1]이 될 것이다
- 이어서 n이 2라면 계단은 2개일 것이고, 이전 계단과 현재 계단의 수만이 얻을 수 있는 점수일 것이다
- 따라서 dp[2] = arr[1] + arr[2]일 것이다
- 그럼 이후의 값은 어떻게 할 수 있을까?
- 연속된 세칸의 계단을 모두 밟아서는 안되며, 한계단, 두계단씩은 오를 수 있다고 하였다
- 이를 식으로 바꿨을 때, 현재의 세번째까지 누적된 dp[i-3]값에
현재의 바로 아래 계단인 arr[i-1]을 더한 값과 |
현재의 두번째 아래인 계단의 누적된 dp[i-2]중 큰 값을 구하고,
현재 계단의 수인 arr[i]를 더한 값이 현재 계단까지 얻을 수 있는 점수의 최댓값이 될 것이다 - 따라서 점화식은 dp[i] = Math.max(dp[i-3] + arr[i-1], dp[i-2]) + arr[i]가 될것이다!
코드 설계하기
입력값 상태 관리하기
- 크기는 변수로 받고, 입력값들도 int타입의 배열로 받아서 관리한다
- 이때 관리를 조금 편하게 하기 위해 n+1만큼의 크기로 선언하고 1번 인덱스부터 값을 받는다
DP식 구현
- dp도 arr배열처럼 n+1만큼의 크기만큼 선언한다
- 최소 크기는 1이므로 dp[1] = arr[1]은 조건 없이 넣어준다
- dp[2]는 크기가 1일때 ArrayIndexOutofRange 에러가 발생할 수 있으니
n의 크기가 2보다 클때 dp[2] = arr[1] + arr[2]를 넣어주자 - 이후 3부터 시작해서 n+1보다 작을 때까지 점화식을 실행해서 값을 누적해주자
출력 설계하기
- 우리가 구하려고하는 도착지점 n번 인덱스의 dp값인 dp[n]을 출력하면 정답이 된다!
정답 코드
(1회차 시도 성공!)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n+1];
for (int i = 1; i < n+1; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
int[] dp = new int[n+1];
dp[1] = arr[1];
if(n >= 2){
dp[2] = arr[1] + arr[2];
}
for (int i = 3; i < n + 1; i++) {
dp[i] = Math.max(dp[i-3] + arr[i-1], dp[i-2]) + arr[i];
}
bw.write(dp[n]+"");
br.close();
bw.close();
}
}
문제 링크
Software Developer