[JAVA] 2579번 - 계단 오르기

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

직접 그려서 규칙을 찾아보았다. 그래도 처음 DP풀때에 비하면 아주 조금 풀수있게 되었다.. 아주 조금..

근데 100프로 제대로 한건 아니고 한 70프로는 그래도 푼것같다

내가 간과해서 찾지 못한건 다음과 같다.

세칸 연속으로 오를 수 없는거!!

두계단씩 오르는 규칙은 제대로 찾았는데 한 계단씩 오르는 부분의 규칙에서 오류가 있었다.

먼저 세칸을 연속으로 오를 수 없기에 i-1에서 올때는 그 전에는 i-3에서 무조건 와야한다! 이걸 고려못했다

그리고  dp[i-1]라고 했었는데 arr[i-1]이 되어야한다. 

dp[i-1]을 사용하게 되면 i-1번째 계단을 반드시 밟는다는 보장이 사라진다!! 

dp[i-1]는 i-1번째 계단까지의 최대 점수를 의미하기때문이다 이건 i-1번째 계단을 안 밟아도 최대점수를 만들 수 있기 때문

그래서 arr[i-1]을 더해야한다 그래야 그 계단의 점수를 더하는거니까 완전히 계단을 밟는것이기 때 문

=> 출발지점에서는 dp배여링고 더하는 값은 arr이다 

 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

1. dp배열을 만들고 입력을 받는다 

2. 미리 저장할 값은 저장한다

3. 나머지 값은 for문 돌리면서 dp배열의 값을 갱신한다

4. 출력

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

 

if문 걸어줘야 런타임 에러가 안난다 첫시도에서 if문 안걸어서 런타임에러남 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;

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[]arr = new int[n+1]; 
        
        for(int i=1; i<=n; 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; i++) {
        	dp[i] = Math.max(dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i]);
        }
        System.out.println(dp[n]);
        
    }
}