https://www.acmicpc.net/problem/1173
<코드>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int N, start_m, max_M, T, R;
// 운동하는 시간, 초기 맥박, 최대 맥박, 추가된 맥박, 감소된 맥박
cin>>N>>start_m>>max_M>>T>>R;
int min = start_m;
if(max_M-start_m<T)
{
cout<<-1<<'\n';
}
else
{
int time=0;
while(N)
{
if(start_m+T<=max_M)
{
start_m += T;
N--;
time++;
}
else
{
if(start_m - R <= min) start_m = min;
else start_m -= R;
time++;
}
}
cout<<time<<'\n';
}
}
<풀이 과정>
단순 그리디 구현 문제이다.
우선적으로 운동을 1분했을때의 맥박 증가량 > (최대맥박 - 최소맥박) 이면, 운동을 할 수가 없기에 이 부분을 제외시켜줘야 한다.
그 이후에, Greedy하게 접근해야한다. 만약, 운동을 할 수 있으면 맥박을 증가시켜주고 운동시간을 1분 줄이고 전체 걸리는 시간을 1분 증가시켜줘야 한다. 그렇지 않고 휴식을 취한다면 전체 시간만 1분 증가시켜주면 된다.
그리고 추가적으로, 기존 맥박 - 맥박 감소량 < 최소 맥박인 경우에는 최소맥박으로 바꿔주는 과정이 필요하다.
'PS > 그리디 알고리즘[Greedy]' 카테고리의 다른 글
백준 2138 전구와 스위치(c++) (1) | 2023.01.31 |
---|---|
백준 1080 행렬(c++) (0) | 2023.01.31 |
백준 3135 라디오(c++) (0) | 2022.09.18 |
백준 20044 Project Teams(c++) (0) | 2022.09.18 |
백준 2170 선 긋기(c++) (0) | 2022.08.06 |