사용자 도구

사이트 도구


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()

토론

댓글을 입력하세요:
U B I H M
 
ps/problems/boj/15600.txt · 마지막으로 수정됨: 2023/06/20 15:31 저자 teferi