[BOJ] 2579 계단 오르기 - JAVA

1. 문제

2579번: 계단 오르기

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

---

2. 풀이

• stairs[N][0]에는 N번째 칸을 밟으면 얻을 수 있는 점수를 저장한다.
• stairs[N][1]에는 N-1칸을 밟은 뒤 N번째 칸을 밟으면 얻을 수 있는 점수를 저장한다. 이 때, stairs[N-1][2] 값만 더할 수 있다. [N-1][1]은 N-2, N-1칸을 밟아온 점수라서 N칸까지 밟는다면 연속된 세 개의 계단을 밟는 것이 되기 때문이다. N-3, N-1, N칸 경로만 가능하다.
• stairs[N][2]에는 N-2칸을 밟은 뒤 N번째 칸을 밟으면 얻을 수 있는 점수를 저장한다. N-2에서 N칸을 간다면 N-2칸이 어떤 칸을 밟고 왔는지 상관없다. 따라서 [N-2][1], [N-2][2] 중에서 큰 값을 찾아서 그 값과 N칸의 점수를 더한다.

public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   int N = Integer.parseInt(in.readLine());

   int[][] stairs = new int[N][3];

   for(int i=0;i<N;i++){
      stairs[i][0] = Integer.parseInt(in.readLine());

      if(i>0) stairs[i][1] = stairs[i-1][2];
      stairs[i][1] += stairs[i][0];

      if(i>1) stairs[i][2] = Math.max(stairs[i-2][1],stairs[i-2][2]);
      stairs[i][2] += stairs[i][0];
   }

   System.out.println(Math.max(stairs[N-1][1],stairs[N-1][2]));
}

---

3. 결과