1173번 운동

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

2가지 방법이 있다.  시뮬레이션, BFS

[시뮬레이션]

운동은 맥박을 고려해야한다.(M을 초과하면 안 됨) 

그러나 휴식은 무조건 가능하므로(M-R < m 이더라도, m으로 무조건 가능.)

m + T > M의 경우만 고려하면 된다.

[BFS]

시간이 중복되지 않게 방문 처리한다.

물론 BFS인 경우 배열의 범위를 초과하면 안 된다.

문제에서는 통과가 된다.

시뮬레이션

#include <bits/stdc++.h>
 
using namespace std;
 
int N, m, M, T, R, t, ec, h;
/*
t : 시간, ec : 운동 횟수, h, 맥박
*/
 
int main(void)
{
    scanf("%d %d %d %d %d", &N, &m, &M, &T, &R);
 
    h = m;
 
    if (m + T > M) {
        printf("-1\n");
        return 0;
    }
 
    while (ec < N) {
        if (h + T <= M) h += T, ++ec, ++t;    
        else h = h - R < m ? m : h - R, ++t;    
    }
 
    printf("%d\n", t);
 
    return 0;
}

BFS

#include <bits/stdc++.h>
 
using namespace std;
 
typedef struct info
{
    int t, h, ec; // 시간, 맥박, 운동 횟수
}info;
 
int N, m, M, T, R;
 
bool visit[200000];
 
int bfs()
{
    if (m + T > M) return -1;
 
    int ret = 0;
 
    queue<info> q;
 
    q.push({ 0, m, 0 });
 
    while (!q.empty())
    {
        int t = q.front().t; // 시간
        int h = q.front().h; // 맥박
        int ec = q.front().ec; // 운동 횟수
 
        if (N <= ec) return t;
 
        q.pop();
 
        if (visit[t + 1]) continue;
 
        visit[t + 1] = true;
 
        if (h + T <= M) q.push({ t + 1, h + T, ec + 1 });
 
        int bt = h - R < m ? m : h - R;
 
        q.push({ t + 1, bt, ec });
    }
 
    return -1;
}
 
int main(void)
{
    int t = 0;
 
    scanf("%d %d %d %d %d", &N, &m, &M, &T, &R);
 
    printf("%d\n", bfs());
 
    return 0;
}