BOJ 백준 5014 스타트링크

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

5014번: 스타트링크

문제 풀이 )

 

    1. DP를 통한 풀이 ( 메모리, 시간 효율이 낮은 풀이 )

#include <cstdio>

#define TOTAL 0
#define START 1
#define DEST 2
#define UP 3
#define DOWN 4

#define SIZE 1000010

using namespace std;

int input[5] = { 0 };
int dp[SIZE] = { 0 };

void solution(int nCurFloor, int nDestFloor, int nCount)
{
	if (nCurFloor > input[TOTAL] || nCurFloor < 0) return;
	
	if (dp[nCurFloor] != 0 && dp[nCurFloor] <= nCount) return;

	dp[nCurFloor] = nCount;

	solution(nCurFloor + input[UP], nDestFloor, nCount + 1);
	solution(nCurFloor + input[DOWN], nDestFloor, nCount + 1);
}

int main()
{
	scanf("%d %d %d %d %d", 
		&input[TOTAL], &input[START], &input[DEST], &input[UP], &input[DOWN]);

	input[DOWN] = -input[DOWN];

	if (input[START] == input[DEST])
	{
		printf("0\n");
		return 0;
	}
	
	solution(input[START], input[DEST], 0);

	if (dp[input[DEST]] != 0) printf("%d\n", dp[input[DEST]]);
	else printf("use the stairs\n");

	return 0;
}

 

    2. 다른 풀이

 

    건물의 최대 층수까지 1층씩만 오른다고 가정했을 때,

최대 건물의 최대 층수만큼의 횟수 이전까진 도착해야할 층에 도달해야 한다.

 

    현재 내가 있는 층이 도착해야할 층보다 높거나 더 이상 올라가지 못하는 경우 내려가야 한다.

내려가는 것이 강제되었는데 0층 미만으로 내려가진다면, 도착할 수 없는 층임을 의미한다.

#include <cstdio>

#define TOTAL 0
#define START 1
#define DEST 2
#define UP 3
#define DOWN 4

using namespace std;

int input[5] = { 0 };

int main()
{
	scanf("%d %d %d %d %d", 
		&input[TOTAL], &input[START], &input[DEST], &input[UP], &input[DOWN]);

	int nCurFloor = input[START];

	for (int i = 0; nCurFloor > 0 && nCurFloor <= input[TOTAL] && i <= input[TOTAL]; i++)
	{
		if (nCurFloor == input[DEST])
		{
			printf("%d\n", i); return 0;
		}

		if (nCurFloor > input[DEST] || nCurFloor + input[UP] > input[TOTAL]) nCurFloor -= input[DOWN];
		else nCurFloor += input[UP];
	}
	printf("use the stairs\n");

	return 0;
}