[백준] 운동

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

1173번: 운동

 

 

< 문제 설명 >

운동을 N분 하는데 필요한 시간의 최솟값을 출력해라.

N, m, M, T, R이 주어진다.

N : 운동 시간

m : 초기 맥박이자 최소 맥박. 맥박은 m보다 작아질 수 없다.

M : 최대 맥박. 맥박은 M을 넘으면 안된다.

T : 운동 시 추가되는 맥박크기

R : 휴식 시 감소되는 맥박 크기

 

현재맥박+T가 M보다 작거나 같을 때만 운동을 할 수 있다.

휴식해서 현재맥박-R이 m보다 작아진다면 m이 된다.

운동을 할 수 없으면 -1을 리턴.

 

 

< 문제 이해 >

처음에는 단순하게 운동시간에 맞게 증가하는 맥박을 전부 구해서

휴식을 해야하는 횟수를 구하고 휴식 횟수와 N을 더해주면 된다고 생각했다.

그러나 잘 풀리지  않아 while문을 이용해 문제를 풀었다.

 

 

< 시행 착오 >

import math

N, m, M, T, R = map(int, input().split())

if m+T > M :	# 운동을 하지 못하는 경우
    print(-1)

else:
    if m+N*T <= M : print(N)	# 휴식이 필요하지 않은 경우
    else:						# 휴식 필요한 경우
        if M-m < R:					# 감소 맥박이 최대 최소 맥박의 차이보다 작을 때
            print(N + math.ceil((N*T-(M-m)//T*T)/(M-m)))
        else:						# 감소 맥박이 최대 최소 맥박의 차이보다 작을 때
            print(N + math.ceil((N*T-(M-m)//T*T)/R))

먼저 운동할 때 증가되는 맥박이 최대를 넘어가면 운동을 할 수 없기 때문에 -1을 리턴한다.

그렇지 않을 경우를 3가지로 나누어 보았다.

첫번 째는 휴식이 필요 없을 경우(N번 운동해도 최대맥박을 넘지 않는 경우),

두번 째는 휴식이 필요한데, 휴식 시 감소되는 맥박이 최대 심박과 최소 심박의 차이보다 작을 때,

세번 재는 휴식이 필요한데, 휴식 시 감소되는 맥박이 최대 심박과 최소 심박의 차이보다 클 때이다.

식은 N*T에서 처음 최대 맥박 이하에 도달하는 매박을 빼주고 R로 나누어 횟수를 구하는 것이다.

그러나 실패했다,,

끝까지 해결해보려했는데 반례를 찾지 못했다,,,,,,,,

 

 

< 문제 풀이 >

import math

N, m, M, T, R = map(int, input().split())

now = m		# 현재 맥박
idx = 0		# 몇번째 운동인지
Rcnt = 0	# 회복 카운트

if m + T > M:	# 운동을 하지 못하는 경우
    print(-1)

else:
    while idx < N:
        if now + T <= M:	# 최대 맥박을 넘지 않으면 운동
            idx += 1
            now += T
        else:			# 최대 맥박을 넘으면 휴식
            Rcnt += 1
            now -= R if now-R >= m else now-m	# 휴식 후 맥박이 m보다 작아지면 now가 m

    print(N+Rcnt)

요로코롬 해결할 수 있었다.

 

 

 

위에 풀이로도 해결할 수 있을 것 같았는데 자꾸 미련이 남는다,,,

다음 번에 다시 풀어보도록 하겠다!

쉬운 문제지만 나중에 다시 풀어보기 위해 여기에 박제ㅎㅎ