2일차 TIL
오늘의 학습 키워드
먼저 생각하고 코드 작성, 수식 활용하기
오늘의 회고
문제
오늘 문제는 수식으로 표현만 잘 하면 크케 어려운 부분은 없었다.
사고과정은 다음과 같다.
간격이 늘어나는 상태로 + 가장 많은 간격 횟수를 구해야한다.
처음 간격을 a라고 하면, 최소 간격은
a,a+1,a+2,a+3,a+4 ..... 이런식으로 갈것이다.
가장 마지막 도착지를 k라고 하고, max 간격 횟수를 m번이라고 하면
a+(a+1)+(a+2)+...(a+m−1)=k 라는 식이 성립된다.
정리하면
ma+((m−1)+1)×(m−1)/2=k 이고 한단계 간격을 +1로 최소한의 간격을 표현한것이기 때문에
ma+((m−1)+1)×(m−1)/2<=k 로 표현 할 수 있다.
우리는 m의 최댓값을 구하는 것이기 때문에
k−((m−1)+1)×(m−1)/2>=m 이 성립하는 m의 최댓값을 구하면 된다.
그런데, m의 최댓값을 구하는 과정에서 1부터 시작하거나 k부터 시작하면 시간이 너무 오래 걸릴 가능성이 있기때문에, 시작점을 잘 설정하는것이 중요하다.
ma+((m−1)+1)×(m−1)/2 <= k이 식에서
((m−1)+1)×(m−1)/2<=k 이고,
((m−1)+1)×(m−1)<=2k 이므로,
((m−1)+1)×(m−1)<=m2<=2k 이기 때문에
m을 2k 의 정수부분으로 잡고, 1씩 감소하여 만족하는 m값이 나타날 때까지 과정을 반복하는 식으로 설정하니 시간을 보장할 수 있었다.
내가 구현한 식은 다음과 같다.
