5014 스타트링크

문제 링크

• 내 풀이

이동했던 위치를 기록하고 중복이동 하지 않도록 막고 큐에 이동 횟수와 위치를 기록했다.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <queue>

using namespace std;

int F, S, G, U, D;
int ck[1000001];

int solve()
{
    queue<pair<int, int>> q;

    q.push({ S, 0 });
    ck[S] = 1;

    while (!q.empty())
    {
        int cur = q.front().first;
        int cnt = q.front().second;
        q.pop();

        if (cur == G)
            return cnt;

        cnt += 1;
        if (cur + U <= F && !ck[cur + U])
        {
            q.push({ cur + U, cnt });
            ck[cur + U] = 1;
        }
        if (cur - D > 0 && !ck[cur - D])
        {
            q.push({ cur - D, cnt });
            ck[cur - D] = 1;
        }
    }

    return -1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> F >> S >> G >> U >> D;

    int ans = solve();
    if (ans == -1)
        cout << "use the stairs\n";
    else
        cout << ans << "\n";

    return 0;
}

• 다른 사람 풀이

(S가 G보다 작으며 S + U가 F보다 작음) OR (S가 G보다 크고 S - D가 1보다 작으면) UP 버튼을 누른다. 이외에는 DOWN 버튼을 누른다.

가장 적은 방법으로 이동하는 방법임을 귀납적으로 추론해야하는데 잘 안된다.

사칙 연산 중 덧셈과 뺼셈의 순서는 결과에 영향이 없음을 알면 된다!! 히히!

그러니 저번 코테에 나온 문제처럼 현위치 부터 2배 이동 같은 경우는 큐를 이용하여 문제를 풀어야 한다. (곱셈의 결과는 순서에 영향을 받음)

#include <cstdio>

int main()
{
    int F, S, G, U, D, n;
    scanf("%d%d%d%d%d", &F, &S, &G, &U, &D);
    for (n = 0; n < 1000000; n++)
    {
        if (S == G)
        {
            printf("%d", n);
            return 0;
        }
        if (S + U > F && S - D < 1) break;
        if (S < G && S + U <= F || S > G && S - D < 1) S += U;
        else S -= D;
    }
    puts("use the stairs");
}