BOJ 19639번: 배틀로얄

2021. 1. 16. 03:16· 알고리즘💻/그리디

www.acmicpc.net/problem/19639

 

19639번: 배틀로얄

첫 번째 줄에 X, Y, M (0 ≤ X, Y ≤ 100,000, 2 ≤ M ≤ 100,000)이 주어진다. M은 짝수다. 다음 X개의 줄에는 i번째 사람과 싸웠을 때 잃게 되는 체력이 주어진다. 이 수는 0 이상 M / 2 이하의 정수이다.

www.acmicpc.net

아이디어:

어려웡..

1. 포션은 체력이 m//2보다 같거나 작은 경우에만 섭취

2. 그러면 데미지의 합 > 초기 체력m+회복 합 인 경우를 걸러내면 불가능한 경우 걸러낼 수 있음.

3. 플레이어를 돌아가면서 데미지를 받고, 남은 체력이 m//2보다 같거나 작은 경우 체력이 m//2보다 같거나 크게 될때까지 포션 섭취. 만약 포션이 없으면 그대로 진행.

4. 플레이어를 다 돈 후 포션이 남으면 남은 포션 출력

 

생각해볼 점: 저 굵은 글씨 친 부분을 생각하지 못해서 삽질했다. 남이 짠 코드를 보면서 로직을 이해할 때는 제대로 보자.. 대충 훑지 말고^^

 

코드:

import sys
x, y, m = map(int, sys.stdin.readline().split())
damage = []
heal = []
t_damage = 0
t_heal = m
M = m//2
for i in range(x):
    a = int(sys.stdin.readline())
    damage.append([a, i+1])
    t_damage+=a
    
for i in range(y):
    a = int(sys.stdin.readline())
    heal.append([a, i+1])
    t_heal+=a

#게임에서 이길 방법이 없는 경우
if (t_damage >= t_heal):
    print(0)
    sys.exit(0)
    
#내림차순으로 정렬
damage.sort(key = lambda x:-x[0])
heal.sort(key = lambda x:-x[0])

j=0
for i in range(x):
    m -= damage[i][0]
    print(damage[i][1]*-1)
    if (m<=M and j<y):
        while(j<y):
            m+=heal[j][0]
            print(heal[j][1])
            j+=1
            if (m>M): break

if (j<y):
    for k in range(j,y, 1):
        print(heal[k][1])

'알고리즘💻 > 그리디' 카테고리의 다른 글

BOJ 1758번: 알바생 강호  (0) 2021.04.06
BOJ 2828번: 사과 담기 게임  (0) 2021.04.06
BOJ 13904번: 과제  (0) 2021.01.16
BOJ 12931번: 두 배 더하기  (0) 2021.01.16
BOJ 11047번: 동전 0  (0) 2021.01.15
'알고리즘💻/그리디' 카테고리의 다른 글
  • BOJ 1758번: 알바생 강호
  • BOJ 2828번: 사과 담기 게임
  • BOJ 13904번: 과제
  • BOJ 12931번: 두 배 더하기
호프
호프
호프
Untitled
호프
전체
오늘
어제
  • 분류 전체보기 (341)
    • 오류😬 (4)
    • 스터디📖 (96)
      • 웹 개발 기초 (8)
      • Spring (20)
      • ML, DL (30)
      • Node.js (22)
      • React (0)
      • 블록체인 (12)
      • Go (3)
      • Javascript (1)
    • 알고리즘💻 (153)
      • 그리디 (23)
      • Bruteforce&Backtracking (16)
      • DP (17)
      • 이분탐색&정렬&분할정복 (17)
      • 누적합&투포인터 (6)
      • 스택&큐&덱 (19)
      • 그래프(DFS&BFS) (19)
      • 트리 (7)
      • 우선순위큐&다익스트라 (11)
      • 벨만포드&플로이드와샬 (8)
      • map&set&number theory (5)
      • 기타 (5)
    • 프로젝트 (3)
      • 캡스톤 디자인 프로젝트 (3)
    • 블록체인🔗 (3)
      • Solana (2)
      • 개발 (0)
      • Harmony (1)
    • ASC (6)
    • CS (73)
      • 데이터베이스 (12)
      • 클라우드컴퓨팅 (21)
      • 운영체제 (11)
      • 컴퓨터네트워크 (14)
      • 블록체인응용 (15)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 복습

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
호프
BOJ 19639번: 배틀로얄
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.