ps:problems:boj:15600
목차
Boss Battle
ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 15600 |
문제명 | Boss Battle |
레벨 | 브론즈 1 |
시간복잡도 | O(1) |
사용한 언어 | Python 3.11 |
제출기록 | 31256KB / 40ms |
최고기록 | 32ms |
해결날짜 | 2023/06/20 |
풀이
- 보스의 위치의 후보를 연속된 점들이 되도록 유지하자.
- 폭탄을 던지면 보스의 위치의 후보들중 3군데를 체크할수 있다. 폭탄을 던져도 위치의 후보가 연속되게 유지 하려면, 폭탄은 위치 후보중 끝에서 두번째에 던저야 한다
- 보스가 살아남았다면, 가능한 위치중에서 3군데가 제외된다. 이후 보스가 한칸씩 이동할수 있으므로, 가능한 위치는 2군데가 추가된다. 결국 한스텝이 지날때마다 가능한 위치는 1개씩 줄어든다.
- 가능한 위치가 3개 이하이면 한번의 폭탄으로 찾을수 있다.
- 결국 최악의 경우에도 max(1, n - 2)번의 폭탄으로 보스를 잡을수 있다.
코드
"""Solution code for "BOJ 15600. Boss Battle".
- Problem link: https://www.acmicpc.net/problem/15600
- Solution link: http://www.teferi.net/ps/problems/boj/15600
"""
def main():
n = int(input())
print(max(1, n - 2))
if __name__ == '__main__':
main()
ps/problems/boj/15600.txt · 마지막으로 수정됨: 2023/06/20 15:31 저자 teferi
토론