[백준] 2579번 계단 오르기 JAVA (자바) 풀이
문제 2579번 (DP)
: 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다
계단 오르는 규칙
- 한 번에 한 계단씩 또는 두 계단씩 오르기
- 연속된 세 개의 계단을 모두 밟아서는 안 된다 (단, 시작점은 미포함)
- 마지막 도착 계단은 반드시 밟아야 한다
총 점수의 최댓값을 구하는 프로그램을 작성하시오
[입력]
: 입력의 첫째 줄에 계단의 개수
둘째 줄부터 한 줄에 하나씩 계단 점수
(계단 개수는 300이하의 자연수, 계단 점수는 10,000이하의 자연수)
[출력]
: 첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력
[설명]
DP 알고리즘
: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법
DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다
| 탑다운 (Top-Down) | 보텀업 (Bottom-Up) |
| 작은 크기로 문제를 나눠서 해결 | 작은 것부터 해결해서 점차 빌드업 |
| 메모제이션 (memoization) | 타뷸레이션 (tabulation) |
| 일부만 계산해도 답이 나올 때 | 모두 계산해야 답이 나올 때 |
| 재귀 | 반복문 |
| 시간 복잡도 O(n) | 시간 복잡도 O(n) |
1. N인 현위치는 무조건 밟아야 한다
- 현위치는 반드시 밟아야 하므로 이전 계단에서 어느부분을 건너 뛸 지 고민하기
- 이전 3개의 계단에서 2칸씩 뛰어서 올 것인지 1칸-3칸 번갈아가며 올 것인지 결정
- dp[4]
- dp[i-2] = dp[2] 두칸씩 뛰어 현지점 도착
- dp[i-3] + score[i-1] = dp[1] + score[3] 1번째 계단에서 3번째 계단으로 갔다가 현지점 도착
[코드]
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));
int N = Integer.parseInt(br.readLine());
int score[] = new int[N+1];
int dp[] = new int[N+1];
for(int i=1;i<=N;i++){
score[i] = Integer.parseInt(br.readLine());
}
dp[1] = score[1];
if(N>1) dp[2] = score[1]+score[2];
if(N>2) dp[3] = Math.max(score[1], score[2]) + score[3];
for(int i=4;i<=N;i++){
dp[i]= Math.max(dp[i-3]+score[i-1], dp[i-2]) + score[i];
}
System.out.println(dp[N]);
}
}
[해설]
: BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int score[] = new int[N+1]; 계단점수 입력 따로 받기
int dp[] = new int[N+1]; dp 배열
: for(int i=1;i<=N;i++){ 계단 1부터 점수 계산
score[i] = Integer.parseInt(br.readLine());
}
: dp[1] = score[1]; 1번 계단
if(N>1) dp[2] = score[1]+score[2]; 1-2 연속 계단
if(N>2) dp[3] = Math.max(score[1], score[2]) + score[3]; 1-3 계단 / 2-3 계단 중 최대값
for(int i=4;i<=N;i++){ 계단 4부터 계산
dp[i]= Math.max(dp[i-3]+score[i-1], dp[i-2]) + score[i];
현재 계단을 제외하고 이전 계단까지 생각했을 때
연속된 3개중 1번째 3번째 밟고 현위치로 올 건지
2번째 밟고 현위치로 올 건지 고민
}
: System.out.println(dp[N]); 결과 출력
이제 풀어보러 갈께요 :)
* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *