Baekjoon - 2579

문제

Solved.ac Class3

1차시도

public class Main {

	private static int max;
	private static int[] stairs;
	private static int size;

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

		size = Integer.parseInt(br.readLine());
		stairs = new int[size + 1];
		max = Integer.MIN_VALUE;

		for (int i = 1; i < size + 1; i++) {
			stairs[i] = Integer.parseInt(br.readLine());
		}

		solve(0,1,true);
		solve(0,2,true);

		System.out.println(max);
	}

	private static void solve(int beforePoint, int now, boolean jumpOnce) {
		int nowPoint = beforePoint + stairs[now];

		if (now == size) {
			if (max < nowPoint) {
				max = nowPoint;
			}
			return;
		}

		if (jumpOnce && now + 1 <= size) {
			solve(nowPoint, now + 1, false);
		}
		if (now + 2 <= size) {
			solve(nowPoint, now + 2, true);
		}

	}
}

시간초과

2차시도

DP를 적용, Bottom - Up 방식

public class Main {

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

		int size = Integer.parseInt(br.readLine());
		int[] stairs = new int[size + 1];
		int[] data = new int[size + 1];

		boolean isJumpOnce = true;

		for (int i = 1; i < size + 1; i++) {
			stairs[i] = Integer.parseInt(br.readLine());
		}

		data[1] = stairs[1];

		for (int i = 2; i < size + 1; i++) {
			if (isJumpOnce) {
				data[i] = data[i - 1] + stairs[i];
				isJumpOnce = false;
			}
			if (data[i] <= data[i - 2] + stairs[i]) {
				data[i] = data[i - 2] + stairs[i];
				isJumpOnce = true;
			}
		}
		System.out.println(data[size]);
	}
}

실패

3차시도

마지막 계단은 꼭 밟아야 한다는 규칙이 있다.
위 코드대로 진행할 경우, 마지막 계단을 밟지 않고 도착하는 경우가 생긴다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

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

		int size = Integer.parseInt(br.readLine());
		int[] stairs = new int[size + 1];
		int[] data = new int[size + 1];

		for (int i = 1; i < size + 1; i++) {
			stairs[i] = Integer.parseInt(br.readLine());
		}

		data[1] = stairs[1];

		if (size >= 2) {
			data[2] = stairs[1] + stairs[2];
		}

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

		System.out.println(data[size]);

	}
}

변경사항

boolean 을 확인하지 않고 검색
이전에는 2번 연속 계단을 1번 올랐는지 확인하는 과정을 거쳤다.
이번에는 이전 계단을 올랐으면, 그전에는 무조건 두 계단을 올랐을 것이다. 따라서 그 부분이 바뀌었다.

target의 값을 구하려면

1. 노란색(2계단 오르기) + 현재 계단 = 10 + 15
2. 초록색(1계단 오르기, 이 경우 2번 이전에는 무조건 2번 뛰어서 계단을 건너야 한다) + 현재 계단 = 0 + 20 + 15

성공