[백준알고리즘] 2579번: 계단 오르기 -C, Python

[백준알고리즘] 2579번: 계단 오르기 -C, Python

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

이전에 풀었던 문제인데 새로 풀어보았다. 이전에 C로 풀었었는데 포스팅을 안 해서 같이 올리려고 한다.

 

우선 이번에 풀었던 방식은 간단하다. 연속으로 3개의 계단을 오를 수 없고 마지막 계단은 항상 밟아야 하기 때문에 각 계단을 밟을 때의 최댓값을 유지하고 N번 계단에서의 최댓값을 구하면 된다.

 

연속으로 3개의 계단은 밟을 수 없고 다음칸 혹은 다다음칸을 밟을 수 있기 때문에 두 경우를 모두 유지해줬다.

같은 말이지만 다르게 말하면 i번째 칸을 밟으려면 i-1번째에서 밟거나 i-2번째에서 밟아야 한다. 하지만 i-1번째에서는 i-2번째를 밟은 상태가 아닌 i-3번째를 밟은 상태여야 한다. 그렇기 때문에 stairs_jmp라는 두 칸을 뛰어서 밟은 경우의 최댓값을 유지하는 리스트를 하나 더 생성하게 되었다.

 

우선 리스트 stairs는 초기 값을 입력 받고 i-1번째 계단으로부터 밟는 것을 유지한다. 하지만 i-1번째 계단으로부터 밟아야 하지만 i-2번째 계단은 밟지 않은 상태여야 하기 때문에 stairs_jmp[i-1]의 누적 값을 사용한다.

 

여기서 staris_jmp는 i번째 계단을 밟기 위해서는 i-1번째 계단이 아닌 i-2번째 계단으로부터 밟은 것으로 i-2번째 계단은 i-3번째에서부터 밟던 i-4번째 계단에서부터 밟던 상관이 없는 상태이다. 따라서 max(stairs[i-2], stairs_jmp[i-2])의 값이 더해지게 된다.

 

최종적으로 max(stairs[N], stairs_jmp[N])가 최댓값이 된다.

 

import sys

N = int(sys.stdin.readline())
stairs = [0]
stairs += [int(sys.stdin.readline()) for _ in range(N)]

stairs_jmp = stairs[:]
for i in range(2, N+1):
    stairs[i] += stairs_jmp[i-1]
    stairs_jmp[i] += max(stairs[i-2], stairs_jmp[i-2])

sys.stdout.write(str(max(stairs[N], stairs_jmp[N])))

 

아래는 이전에 C로 풀었을 때의 코드이다. 역시 C는 너무 길다.. 예전에 풀 때는 블로그에 올릴 생각 없이 했기 때문에 더 지저분하게 푼 것도 있는 것 같다..

 

여기서는 각 인덱스에서의 max값을 유지하기 위해서 max[i-2] + score[i]와 max[i-3] + score[i-1] + score[i]를 비교함으로써 값을 채워나갔다. 역시 2칸 전에서 왔는지, 1칸 전에서 왔는지 비교하기 위한 방식이다. 이번에 푼 방식과 같은 방식이기는 하지만 더 깔끔하게 짤 수 있었을 텐데... 아쉽다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void) {
	int i = 0, stair = 0;
	int *score, *max_score;

	scanf("%d", &stair);
	score = (int *)malloc(sizeof(int) * (stair + 1));
	max_score = (int *)malloc(sizeof(int) * (stair + 1));
	
	score[0] = 0;
	for (i = 1; i <= stair; i++) {
		scanf("%d", &score[i]);
	}
	max_score[0] = 0;
	max_score[1] = score[1];
	if (stair == 1) {
		printf("%d\n", max_score[1]);
		free(score);
		free(max_score);
		return 0;
	}
	max_score[2] = score[1] + score[2];
	if (stair == 2) {
		printf("%d\n", max_score[2]);
		free(score);
		free(max_score);
		return 0;
	}
	else {
		for (i = 3; i <= stair; i++) {
			max_score[i] = max_score[i - 2] + score[i] > max_score[i - 3] + score[i - 1] + score[i] ?
				max_score[i - 2] + score[i] : max_score[i - 3] + score[i - 1] + score[i];
		}
		printf("%d\n", max_score[stair]);
		free(score);
		free(max_score);
		return 0;
	}
}

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다