Q2579. 계단오르기

현재 위치한 계단까지의 최대값을 저장하며 앞으로 나아가는 로직.

연속 세칸을 밟을수 없으니, 현재위치에서 2칸 앞으로 가는 경우와 1칸 밟고 2칸 가는 경우를 계산해 나가면 됩니다.

해당 로직의 문제는 한칸 계산이 불가능합니다.

따라서 도착지점의 최대값은 도착 전칸의 최대값에 도착칸의 value를 더하여 max값을 계산하면 됩니다.

또한, 시작점은 0번째에서 시작했다고 가정을 하면 1번과 2번칸을 밟을 수 있으므로,

계산 시작부터 1번과 2번칸의 최대값은 각 칸의 value로 설정합니다.

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q2579 { static int[][] array; public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int maxNum = Integer.valueOf(st.nextToken()); array = new int[maxNum+1][2]; for (int i = 1; i <= maxNum; i++) { st = new StringTokenizer(br.readLine()); array[i][0] = Integer.valueOf(st.nextToken()); } array[1][1] = array[1][0]; array[2][1] = array[2][0]; for (int i = 1; i < maxNum; i++) { if (i+3 <= maxNum) { int tempValue = array[i][1] + array[i+1][0] + array[i+3][0]; if (array[i+3][1] <= tempValue) { array[i+3][1] = tempValue; } } if (i+2 <= maxNum) { int tempValue = array[i][1] + array[i+2][0]; if (array[i+2][1] <= tempValue) { array[i+2][1] = tempValue; } } } if (array[maxNum][1] <= array[maxNum-1][1] + array[maxNum][0]) { array[maxNum][1] = array[maxNum-1][1] + array[maxNum][0]; } System.out.println(array[maxNum][1]); } }