실전 문제 : KART-RIDER (N모 회사)

📌 1. 문제 개요

• 기본 개념: 카트는 초속 1로 달리며 T초 동안 이동합니다.
• 아이템 (신발)이 특정 시점에 등장하고, 일정 시간 동안 속도를 증가시켜줍니다.
• 하지만 신발을 착용하는 데 시간이 소요되며, 이 시간 동안은 정지합니다.
• 신발을 하나만 착용 가능하며, 이전 신발 효과가 끝나거나 중간에 다른 신발로 바꿔 신을 수 있습니다.
• 목표는 T초 동안 최대로 멀리 가는 것!

---

🎮 2. 문제 입력 예시

T = 20; // 총 시간

// 신발 정보 (a, b, c, d)
// 생성시간 a, 장착시간 b, 지속시간 c, 속도 d
3  4  10  3
4  1   4  2
10 2   5  5
15 1   3  7

---

🧠 3. 전략 수립

✔️ Shoe 구조체 설계

struct Shoe {
    int time;   // 생성 시간 (a)
    int start;  // 효과 시작 시간 = a + b
    int end;    // 효과 종료 시간 = a + b + c
    int speed;  // 속도 (d)

    Shoe(int a, int b, int c, int d)
        : time(a), start(a + b), end(a + b + c), speed(d) {}
};

• start ~ end 구간 동안은 speed로 이동 가능
• start 전까지는 장착 중이라 정지 상태

---

✔️ 동적 계획법 적용

DP 문제로 전환하기 위한 사고 흐름:
1. 현재 신발을 선택한 뒤 → 다음 신발까지의 거리 계산 → 다음 신발을 선택한 경우의 결과를 재귀로 더함
2. 이미 계산한 신발 조합은 캐시(cache)를 이용해 저장

---

⚙️ 4. 핵심 로직 설명

🔁 Solve(now) 함수

int Solve(int now) {
    if (now >= shoes.size()) return 0;

    int& ret = cache[now];
    if (ret != -1) return ret;

    Shoe& shoe = shoes[now];

    // 현재 신발로 T까지 이동했을 때 거리
    int dist = (shoe.end - shoe.start) * shoe.speed + (T - shoe.end) * 1;
    ret = max(ret, dist);

    for (int next = now + 1; next < shoes.size(); ++next) {
        Shoe& nextShoe = shoes[next];
        if (nextShoe.time < shoe.start) continue; // 이미 지나친 신발은 못 신음

        int moveDist = 0;

        if (nextShoe.time <= shoe.end) {
            moveDist = (nextShoe.time - shoe.start) * shoe.speed;
        } else {
            moveDist = (shoe.end - shoe.start) * shoe.speed;
            moveDist += (nextShoe.time - shoe.end);
        }

        ret = max(ret, moveDist + Solve(next));
    }

    return ret;
}

---

🧪 5. 전체 코드 구현

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Shoe {
    int time, start, end, speed;
    Shoe(int a, int b, int c, int d)
        : time(a), start(a + b), end(a + b + c), speed(d) {}
};

int T;
vector<Shoe> shoes;
vector<int> cache;

int Solve(int now) {
    if (now >= shoes.size()) return 0;
    int& ret = cache[now];
    if (ret != -1) return ret;

    Shoe& shoe = shoes[now];
    int dist = (shoe.end - shoe.start) * shoe.speed + (T - shoe.end);
    ret = max(ret, dist);

    for (int next = now + 1; next < shoes.size(); ++next) {
        Shoe& nextShoe = shoes[next];
        if (nextShoe.time < shoe.start) continue;

        int moveDist = 0;
        if (nextShoe.time <= shoe.end)
            moveDist = (nextShoe.time - shoe.start) * shoe.speed;
        else {
            moveDist = (shoe.end - shoe.start) * shoe.speed;
            moveDist += (nextShoe.time - shoe.end);
        }

        ret = max(ret, moveDist + Solve(next));
    }

    return ret;
}

int main() {
    T = 20;
    shoes.push_back(Shoe(0, 0, T, 1)); // 기본 상태

    // 신발 정보 삽입
    shoes.push_back(Shoe(3, 4, 10, 3));
    shoes.push_back(Shoe(4, 1, 4, 2));
    shoes.push_back(Shoe(10, 2, 5, 5));
    shoes.push_back(Shoe(15, 1, 3, 7));

    sort(shoes.begin(), shoes.end(), [](Shoe& a, Shoe& b) {
        return a.time < b.time;
    });

    cache = vector<int>(shoes.size(), -1);
    int ret = Solve(0);
    cout << ret << endl;
}

---

📈 6. 실행 결과

• 입력:
  총 시간 ( T = 20 )
  다양한 신발 정보 (생성/장착/효과/속도)

• 출력:
  최대 이동 거리 XX (계산 결과)

---