[C++] 백준 2579번: 계단 오르기

문제 바로가기

⛳문제에서 요구하는 것⛳

1. 일정한 점수가 쓰여 있는 계단이 있다.

2. 계단을 밟으면 그 계단에 쓰인 점수를 얻는다.

3. 한 번에 한 계단 혹은 두 계단씩 오를 수 있다.

4. 연속된 세 개의 계단을 모두 밟으면 안 된다.

5. 마지막 도착 계단은 반드시 밟아야 한다.

6. 얻을 수 있는 총 점수의 최대값을 출력하자

 

🧨주어진 조건🧨

1. 계단의 개수 ≤ 300, 자연수

2. 계단의 점수 ≤ 10,000, 자연수

 

✨내가 처음 생각한 풀이✨

1. 그리디 알고리즘을 적용해보기로 했다.

2. 하지만 구현 후 예제와 비교했을 때 결과 값이 다르다.

3. 이 풀이가 아닌가보다.

 

✨두 번째로 생각한 풀이✨

1. 알고리즘 분류가 DP이길래, DP로 풀기로 했다.

2. N이 1일 땐, 첫 번째 계단의 점수를, N이 2일 땐 첫 번째와 두 번째 계단의 점수 합을 저장했다.

3. 세 번째 부터는 1번 째 전 계단의 누적 점수와 2번 째 전 계단의 누적 점수 중 큰 계단을 선택하여 해당 계단 점수를 합해 저장한다.

  - 1번 째 전 계단을 선택한 경우, 계단을 연달아 밟았음을 표시해준다.

  - 만약, 1번 째 전 계단이 연달아 밟은 것이라면 두 번째 전 계단의 누적 점수와 이번 계단의 점수를 합한 것을 저장한다.

#include <iostream>

#define EL "\n"

#define FOR(i, j) for(int i = 0; i < j; i++)

using namespace std;

int stairs[300];
int scores[300];
bool rapid[300];

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	FOR(i, N)
		cin >> stairs[i];

	FOR(i, N) {
		if (i == 0)
			scores[i] = stairs[i];
		else if (i == 1) {
			scores[i] = stairs[i - 1] + stairs[i];
			rapid[i] = true;
		}
		else {
			if (rapid[i - 1])
				scores[i] = scores[i - 2] + stairs[i];
			else if (scores[i - 1] > scores[i - 2]) {
				scores[i] = scores[i - 1] + stairs[i];
				rapid[i] = true;
			}
			else
				scores[i] = scores[i - 2] + stairs[i];
		}
	}

	cout << scores[N - 1] << EL;

	return 0;
}

 

👓결과와 문제점 분석👓

결과: 틀렸습니다.

1. 첫 번째 계단을 밟지 않는 것이 더 높은 점수를 얻는 경우도 있다.

  - 두, 세번째 계단을 연달아 밟는 경우.

  - 반례로 N = 3일 때, 1 100 100인 경우 답은 200이지만 101을 출력한다.

2. 위의 문제를 해결하기 위해 다음 코드를 for문에 추가했다.

 - N = 3일 때의 경우를 별도로 처리하는 것이다.

else if (i == 2) {
	if (stairs[i - 1] > stairs[i - 2]) {
		scores[i] = stairs[i - 1] + stairs[i];
		rapid[i] = true;
	}
	else {
		scores[i] = stairs[i - 2] + stairs[i - 1];
	}
}

3. 하지만 반례를 찾았다.

 - N = 6일 때, 1 1 0 0 1 1이면 3이 나와야 하지만 4가 출력된다.

 - 오타가 있었다. 위 코드에서 else 블럭에 scores[[i] = stairs[i - 2] + stairs[i]이다.

4. 이를 고치고 제출해도 또 틀렸다. 다른게 문제다.

5. 모르겠다. 그래서 질문글을 올렸다.

 

🎯옳은 풀이🎯

다른 글에서 반례를 찾았다. 그리고 얼마 지나지 않아 어떤 분이 반례를 남겨주셨다.

  - 좌측의 반례에서, 네 번째 계단에서 rapid[2] == true이므로 scores[3] = scores[1] + stairs[3]이다.

  - 하지만 stairs = {4, 6, 9, 6, ... }에서 stairs[0] + stairs[2] > stairs[0] + stairs[1]이다.

  - 더 넓은 범위로 생각해보면 scores[n - 3] + stairs[n - 1] > scores[n - 2]인 경우가 있는 것이다.

  - 따라서 scores[n]의 값은 아래 중 최대값이다. 

    ⅰ. scores[n - 3] + stairs[n - 1] + stairs[n]
    ⅱ. scores[n - 2] + stairs[n]
    ⅲ. scores[n - 1] + stairs[n] (단, rapid[n - 1] == false)

  - 위에서 rapid[n - 1] == true인 경우 ⅰ과 ⅱ 중 큰 값으로 결정된다.

  - 그런데 rapid[n - 1] == false인 경우, scores[n - 1] == scores[n - 3] + stairs[n - 1]이므로 ⅲ은 비교할 필요없다.

  - 따라서,  rapid 배열도 필요없게 된다.

  - 그냥 ⅰ과 ⅱ 중 큰 값으로 정하면 된다.

#include <iostream>

#define EL "\n"

#define FOR(i, j) for(int i = 0; i < j; i++)

using namespace std;

int stairs[300];
int scores[300];

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	FOR(i, N)
		cin >> stairs[i];

	FOR(i, N) {
		if (i == 0)
			scores[i] = stairs[i];
		else if (i == 1)
			scores[i] = stairs[i - 1] + stairs[i];
		else if (i == 2) {
			if (stairs[i - 1] > stairs[i - 2])
				scores[i] = stairs[i - 1] + stairs[i];
			else
				scores[i] = stairs[i - 2] + stairs[i];
		}
		else {
			if (scores[i - 3] + stairs[i - 1] > scores[i - 2])
				scores[i] = scores[i - 3] + stairs[i - 1] + stairs[i];
			else
				scores[i] = scores[i - 2] + stairs[i];
		}
	}

	cout << scores[N - 1] << EL;

	return 0;
}