계단 오르기(2579)

계단 오르기(2579)

import java.io.*;
import java.util.*;

public class Main {

  static int[] score;
  static int[] maxValue;
  
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    
    int n =  Integer.parseInt(br.readLine());
    
    score = new int[n+1];
    maxValue = new int[n+1];
    
    for(int i = 1; i <= n; i++) {
      score[i] = Integer.parseInt(br.readLine()); 
    }
    
    maxValue[1] = score[1];
    if(n >= 2) maxValue[2] = score[1] + score[2];
    
    tTob(n);
    
    sb.append(maxValue[n]);
    
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
  
  public static int tTob(int n) {
    
    if(n <= 2) return score[n];
    
    int res = 0;
    
    int tmp1 = 0, tmp2 = 0;
    
    if(maxValue[n-2] > 0) {
      tmp1 = maxValue[n-2] + score[n];
    } else {
      tmp1 = tTob(n-2) + score[n];
    }
    
    if(maxValue[n-3] > 0) {
      tmp2 = maxValue[n-3] + score[n-1] + score[n];
    } else {
      tmp2 = tTob(n-3) + score[n-1] + score[n];
    }
    
    maxValue[n] = Math.max(tmp1, tmp2);
    
    return maxValue[n];
  }
}

풀이과정

1. 그리드 접근으로 가려고 했었다.
2. 하지만 몇몇 경우에는 그리드 방식으로 접근을 하게되면 문제에서 제시한 조건을 벗어나게 되었다.
3. 조건을 바탕으로 제귀함수로 문제를 풀었다.
4. 시간초과가 발생하였다.
5. n의 증가에 따라 경우의 수를 나열하니 중복되는 루트들이 생겼다.
6. 그래서 중복된 루트의 처리를 생각해보니, 각 계단으로 올 수 있는 최대값을 사용하면 된다는 것을 알게되었다.
7. 여기서 문제가 발생하였다. n-2의 경우는 문제가 안되는데 n-1이 문제가 되었다.
8. n=6일 경우 4에서 6으로 넘어오는 것은 4와 6이 연속된 수가 아니므로 4의 최대값이 3에서 온거든 2에서 온거든 크게 중요치 않았다
9. 하지만 5에서 6으로 넘어오는 것은 5와 6이 연속된 수이므로 5의 최대값이 4에서 온 경우에는 문제가 되었다.
10. 그래서 연속으로 온 것과 건너뛰고 온 것을 어떻게 구분지을까 하다가 2차배열로 풀어보려고 하였다.
11. 그렇게 하니 구분은 되지만 코드를 구현하다보니 너무 복잡하여 정리가 되지 않았다.
12. 그래서 다시 생각을 해보니 어쨋든 5의 경우 3에서 온거에다가 5의 값을 더한거면 된다는 생각이 들었다.
13. 즉 n=6인 경우 4에서 올때는 4의 최대값 + 6의값 , 그리고 5에서 올때는 3의 최대값 + 5의값 + 6의값이 되는 거였다.

- 성공
- 메모리 : 14224 KB
- 시간 : 128 ms

보안점

1. 문제의 조건을 분석할 때, 딱 그 조건에만 따라갈게 아니라
2. 조건에 해당하는 값이 나오는 과정도 생각해봐서 문제를 더 쪼개서 볼 수 있는 능력을 키워야겠다.