백준 - 계단 오르기

문제 설명

계단오를때 점수를 받는다.

계단을 오를때 점수를 받을 수 있는 총 점수를 구하는 문제이다.

단 ,규칙이 존재한다.

1. 연속된 3 계단을 밟아 점수를 얻을 수 없다.
2. 마지막 계단은 반드시 밟아야 한다.

TRY

계단의 최대 입력으로 들어올 수 있는 수는 300이다.

이것은 기본적으로 완전탐색을 한다면 시간 초과가 나올 수 있다.

다이나믹으로 풀어낼 수 있다.

dp[i]=MAX(dp[i-2]+ dp[i-3] + stair[i-1])+ stair[i]

위점화식을 해석하면 현재 계단에서 뒤로 두번째 칸을 밟아왔던 값 ,뒤로 세칸 밟아왔던 값 + 뒤로 한칸 밟은 값 이다.

dp[i-3] + stair[i-1]은 역속된 3칸을 밟지 않아야한다는 조건때문이다.

dp[i-1]만 보면 dp[i-1]이 이미 연속된 2칸을 밟아 왔다면 dp[i-1] + dp[i]를 할 수 없기 때문이다 (규칙: 연속된 3계단 x)

dp[i-1]이 이미 연속된 2칸을 밟았다, 안밟았다? 알 수 있는 있을까? → 단순히 값만 보고는 절대 알 수 없다.

dp[i-3] + stair[i-1]은 완벽히 연속된 3칸을 밟지 않았다는 것을 알 수 있다.

dp[i-3]이 연속된 2칸을 밟아왔다면 stair[i-2]의 값을 더할 수 없을 것이다.(규칙: 연속된 3계단 x ) 하지만 i-3칸 계단에서 i-3에 2번쨰 계단과 더했으니 연속된 3칸을 밟지 않았다는 것을 보장할 수 있다.

풀이

public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(reader.readLine());
		int stairs[] = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			stairs[i] = Integer.parseInt(reader.readLine());
		}

		int dp[] = new int[n + 1];
		dp[1] = stairs[1];

		if (n >= 2)
			dp[2] += stairs[1] + stairs[2];

		for (int i = 3; i <= n; i++) {
			dp[i] = Math.max(dp[i - 2], dp[i - 3]+stairs[i-1]) + stairs[i];
		}

		System.out.println(dp[n]);
	}