백준 23739 - 벼락치기

문제

문제 링크

• N개의 챕터를 순서대로 공부하며, 한 번에 최대 30분씩만 집중할 수 있다.
• 각 챕터는 필요한 시간이 다르고, 한 세션의남은 시간은 다음 챕터에 이어서 사용 가능하다.
• 챕터별로 공부한 시간이 필요한 시간의 절반 이상이면 “절반 이상 공부”한 것으로 인정된다.
• 절반 이상 공부한 챕터 수를 출력하는 문제.

풀이

1. i번째 챕터의 공부시간을 입력받는다.
2. 현재 남은 집중시간(time)으로 해당 챕터를 얼마나 공부할 수 있는지 확인한다.
   • 남은 시간이 챕터 필요 시간의 절반 이상이면 카운팅한다.
3. 챕터 공부 후 남은 집중시간에서 해당 챕터 시간만큼 차감한다.
4. 집중시간이 0 이하가 되면 새 세션을 시작하므로 30분으로 리셋한다.

이 과정을 N번 반복한 후 카운팅한 절반 이상 공부한 챕터 수를 출력한다.

시간복잡도

반복문 한 개가 N번 돌아간다.
내부에서는 상수 시간 연산만 한다.

따라서 전체 시간복잡도는 O(N)

코드

내 제출

후기

중첩 반복문을 써야 하나.. 반복문을 여러개 써야하나..
초반 구현 과정에서 여러 생각이 많이 들었었지만 생각보다 빠르고 간단하게 풀었다.

문제를 읽고 이해하는 능력이 조금씩 익숙해지는게 느껴진다.