백준(BaekJoon) 16434번 풀이 - [AP 프로그래밍 - 6월 과제]

(5월 과제)

2024.03.30 - [프로그래밍/문제 풀이] - 백준(BaekJoon) 1167번 풀이 - [AP 프로그래밍 - 5월 과제]

백준(BaekJoon) 1167번 풀이 - [AP 프로그래밍 - 5월 과제]

 

6월 과제는 클래스입니다. 클래스를 이용하여 백준 16434번을 풀어보도록 하겠습니다.

https://www.acmicpc.net/problem/16434

---

사전 탐구

6월의 주제는 '클래스'를 이용해 문제를 객체지향적으로 풀어보는 것입니다. 클래스에 대해 자세히 알아보고 싶지만 과거의 제가 기특하게도 클래스 관련 내용을 다 정리해두었기에(^^) 이를 다시 쓰도록 하겠습니다. (아싸 날먹)

2024.01.24 - [프로그래밍/파이썬 공부하기] - Python 공부 - 3 (클래스, 메서드, 인스턴스, 객체, 속성)

Python 공부 - 3 (클래스, 메서드, 인스턴스, 객체, 속성)

 

문제를 객체지향적으로 풀어볼 것인데 객체지향이 뭔지 정도는 알아야겠죠. 객체 지향 프로그래밍 (Object-Oriented Programming, OOP)은 프로그래밍에서 필요한 데이터를 추상화시켜 상태와 행위를 가진 객체로 만들고, 객체들 간의 상호작용을 통해 로직을 구성하는 프로그래밍 방법이라고 합니다.

쉽게 설명해 그냥 클래스를 쓰면 객체지향이라고 생각하시면 됩니다.

 

객체 지향이 객체 간의 상호작용에 중점을 둔다고 하면 절차 지향은 순차적인 실행에 중점을 둡니다. 절차 지향 프로그래밍 (Procedural Programming, PP)은 우리가 흔히 짜는 코드처럼 순차적으로 코드가 진행되도록 프로그래밍하는 방법입니다.

---

문제 선정 과정

백준에는 '객체지향을 써서 푸세요~'라고 명시되어있는 문제가 사실상 없습니다. (한 문제 있는데 상태가 좀..) 따라서 그냥 일반적인 문제들 중 객체지향을 이용해 풀면 좋은 문제를 풀어보기로 하였습니다. 제가 이전에 쓴 글에서도 클래스를 설명할 때 게임을 예로 들었듯이, 클래스 등 객체지향의 개념은 주로 게임 쪽에서 쓰입니다. 따라서 백준에 있는 여러 문제들 중, 문제 상황이 게임과 관련되어있는 문제를 찾아보았고, 그 중 이 문제가 맘에 들어 16434번을 풀어보게 되었습니다.

---

문제 풀이 전략

이번 문제는 어떻게 생겼는지 한 번 볼까요?

백준 16434번 - 드래곤 앤 던전

 

문제를 간략히 요약해보자면 용사의 체력 & 공격력, 각 방의 몬스터의 체력 & 공격력, 포션이 증가시켜주는 체력 & 공격력이 주어졌을 때, 용사가 몬스터와 포션이 들어있는 방들을 지난 뒤 N번째 방에 있는 용을 잡고 갇혀있던 공주와 오래오래 살기 위해서 필요한 최소 체력이 얼마인가? 정도로 할 수 있을 듯 합니다.

 

이제 이 문제를 어떻게 풀지 전략을 세워보도록 하겠습니다. 먼저, 클래스를 사용할 것이기 때문에 어떤 클래스를 세울 것이고, 그 안의 속성과 메서드는 무엇으로 할지를 정해야합니다. 저는 방의 클래스를 하나 만들고, 해당 방의 종류 (몬스터인지 포션인지), 체력, 공격력을 속성으로 지정할 것입니다. 또, 용사의 클래스를 하나 만들어 용사의 최대 체력, 현재 체력, 공격력을 속성으로 지정하고 용사가 몬스터와 싸워서 살아남는지를 판별하는 메서드와 포션을 마시고 회복하는 메서드를 만들기로 하였습니다.

 

이후 용사의 최대 체력이 주어졌을 때 용사가 주어진 모든 방을 통과할 수 있는지 판별하는 함수를 제작한 뒤, 이분 탐색을 통해 모든 방을 통과하는데 필요한 최소 체력이 얼마인지를 구하는 함수까지 제작하면 문제를 해결할 수 있을 것 같습니다.

---

알고리즘 설명

이 문제를 풀기 위해 이분탐색을 사용할 것입니다. 이분탐색 알고리즘은 이미 3월 과제로 진행한 적이 있으므로 해당 내용을 참고하시기 바랍니다.

2024.03.23 - [프로그래밍/문제 풀이] - 백준(BaekJoon) 17951번 풀이 - [AP 프로그래밍 - 3월 과제]

백준(BaekJoon) 17951번 풀이 - [AP 프로그래밍 - 3월 과제]

---

문제 풀이 과정

이제 문제를 풀기 위해 코드를 작성해보겠습니다. 먼저, 필요한 라이브러리들을 import 해주어야합니다. (이들이 왜 필요한지는 추후에 설명하겠습니다.)

import sys
import math

 

그리고 먼저 방의 클래스를 제작할 것입니다. 속성은 방의 종류(몬스터 or 포션), 공격력, 체력으로 지정할 것인데 그냥 입력만 받고 별 처리가 없어도 되므로 생성자로 받겠습니다.

class Room :
  def __init__(self, room_type, attack, health) :
    self.room_type = room_type
    self.attack = attack
    self.health = health

 

이후 용사의 클래스도 제작할 것입니다. 마찬가지로 생성자를 통해 최대 체력, 현재 체력, 공격력을 입력받을 것이고 현재 체력의 초기값은 최대 체력이므로 그렇게 초기화해주겠습니다.

class Hero :
  def __init__(self, max_hp, attack) :
    self.max_hp = max_hp
    self.current_hp = max_hp
    self.attack = attack

 

이제 용사 클래스 안에 용사가 어떤 방에 있는 몬스터와 싸워 살아남을 수 있을지 판별하는 메서드를 짜볼 것입니다. 먼저, 용사가 몬스터를 쓰러트리기 위해 공격하는 횟수를 구해볼 것입니다. 공격 횟수는 몬스터의 체력을 용사의 공격력으로 나눈 뒤 이를 올림하여 쉽게 구할 수 있습니다. 올림 함수를 사용하기 위해 math 라이브러리를 import한 것입니다.

 

만약 공격 횟수가 1이 나온다면 용사가 처음에 공격하고 바로 다음 방으로 넘어가므로 용사의 체력에 아무 변화가 없습니다. 따라서 공격 횟수가 1보다 클 때만 용사의 체력을 깎을 것인데, 이때 깎는 양은 용사가 먼저 공격하므로 '(공격 횟수 - 1) * 몬스터의 공격력' 만큼입니다. 이후 깎이고 난 뒤의 체력이 0보다 큰지 작은지를 반환해주면 됩니다.

def fight(self, monster_atk, monster_hp) :
  fight_count = math.ceil(monster_hp / self.attack)
  if fight_count > 1 :
    self.current_hp -= (fight_count - 1) * monster_atk

  return self.current_hp > 0

 

이후에는 용사 클래스 안에 용사가 포션을 마시고 회복하는 메서드를 추가할 것입니다. 이 메서드는 단순하게 용사의 공격력에 포션이 올려주는 공격력을 더하고, 용사의 체력에 포션이 올려주는 체력을 더해주기만 하면 됩니다. 이때 주의할 점은 포션으로 체력을 아무리 올려도 그 때의 체력이 용사의 최대 체력을 넘을수는 없다는 점입니다. 따라서 max 함수를 이용해 용사의 최대 체력과 포션으로 인해 증가된 용사의 체력 중 더 큰 값을 고르게 하였습니다.

def recover(self, hp_gain, atk_gain) :
  self.attack += atk_gain
  self.current_hp = min(self.max_hp, self.current_hp + hp_gain)

 

이제 모든 클래스 구현은 끝났고, 다른 함수들을 구현해보겠습니다. 먼저, 용사의 최대 체력이 주어졌을 때 용사가 주어진 모든 방을 통과할 수 있는지 판별하는 함수를 짜보겠습니다. 먼저 용사의 객체를 하나 만들고 주어진 모든 방들에 대해 방의 종류가 몬스터 방이면 fight 메서드를, 방의 종류가 포션 방이면 recover 메서드를 실행하도록 하였습니다. 그리고 fight 메서드를 실행했을 때 FALSE가 반환된다면, 즉 몬스터와 싸운 뒤 용사의 체력이 0보다 작다면 FALSE를, 별 문제 없이 모든 방을 통과했다면 TRUE를 반환하게 하였습니다.

def survivable(max_hp, initial_atk, rooms) :
  hero = Hero(max_hp, initial_atk)
  for room in rooms :
    if room.room_type == 1 :
      if not hero.fight(room.attack, room.health) :
        return False
    elif room.room_type == 2 :
      hero.recover(room.health, room.attack)

 

이번에는 모든 방을 지나는데 필요한 최소 체력을 찾는 함수를 짜보겠습니다. 이분 탐색을 이용해 찾아줄 것이므로, 탐색의 최솟값과 최댓값, 즉 최소 체력의 최솟값과 최댓값을 지정해주어야 합니다. 최소 체력의 최솟값은 당연히 1일것이고, 최댓값은 최대 개수의 방에 가장 쎈 몬스터들이 들어있다고 했을 때 지나갈 수 있는 체력입니다. 방은 최대 123456개이고, 몬스터의 최대 공격력은 1000000이므로 최소 체력의 최댓값은 123456 * 1000000 = 약 10**12 정도이므로 여러번 공격을 주고받을 것을 고려해 저는 적당히 10**18로 지정하였습니다. (left = 1, right = 10**18로 초기화)

 

이후 탐색을 진행할 체력인 mid를 left와 right의 평균으로 지정한 뒤 이 mid를 매개변수로 survivable 함수를 거치게 하였습니다. 만약 mid의 체력으로 살아남지 못한다면 탐색 범위를 mid의 오른쪽으로 옮기고, mid로 살아남는다면 탐색 범위를 왼쪽으로 옮기게 하면 이 함수 구현도 끝납니다.

def min_hp(N, initial_atk, rooms) :
  left, right = 1, 10**18

  while left < right :
    mid = (left + right) // 2
    if survivable(mid, initial_atk, rooms) :
      right = mid
    else :
      left = mid + 1

  return left

 

마지막으로 데이터들을 입력받고 최소 체력을 구하게 하였습니다. 이때, 입력받는 속도를 좀 줄이기 위해 sys.stdin.readline의 방식으로 입력을 받았고, 이를 위해 sys 라이브러리를 import한 것입니다.

input_data = sys.stdin.readline
N, initial_atk = map(int, input_data().split())
rooms = [Room(*map(int, input_data().split())) for _ in range(N)]

min_hp = min_hp(N, initial_atk, rooms)
print(min_hp)

 

다음은 전체 코드입니다.

import sys
import math

class Room :
  def __init__(self, room_type, attack, health) :
    self.room_type = room_type
    self.attack = attack
    self.health = health

class Hero :
  def __init__(self, max_hp, attack) :
    self.max_hp = max_hp
    self.current_hp = max_hp
    self.attack = attack

  def fight(self, monster_atk, monster_hp) :
    fight_count = math.ceil(monster_hp / self.attack)
    if fight_count > 1 :
      self.current_hp -= (fight_count - 1) * monster_atk

    return self.current_hp > 0

  def recover(self, hp_gain, atk_gain) :
    self.attack += atk_gain
    self.current_hp = min(self.max_hp, self.current_hp + hp_gain)

def survivable(max_hp, initial_atk, rooms) :
  hero = Hero(max_hp, initial_atk)
  for room in rooms :
    if room.room_type == 1 :  # Monster room
      if not hero.fight(room.attack, room.health) :
        return False
    elif room.room_type == 2 :  # Potion room
      hero.recover(room.health, room.attack)
          
  return True

def min_hp(N, initial_atk, rooms) :
  left, right = 1, 10**18

  while left < right :
    mid = (left + right) // 2
    if survivable(mid, initial_atk, rooms) :
      right = mid
    else :
      left = mid + 1

  return left
  
input_data = sys.stdin.readline
N, initial_atk = map(int, input_data().split())
rooms = [Room(*map(int, input_data().split())) for _ in range(N)]

min_hp = min_hp(N, initial_atk, rooms)
print(min_hp)

---

시행착오

알고리즘이 복잡하다거나 한 건 아니라 그렇게 많은 시행착오를 겪지는 않았습니다. 그러나, 처음에 코드를 짰을 때는 input() 함수로 입력을 받아 자꾸 시간 초과가 떴는데, 여러 블로그 등에서 input() 함수로 입력을 받을 때보다 sys.stdin.readline을 이용해 입력을 받는 것이 훨씬 속도가 빠르다는 글을 본적이 있었습니다. 따라서 이를 이용해 입력을 받아보니 다행히 시간초과가 뜨지 않고 문제가 잘 해결되었습니다. 앞으로 문제를 풀 때 시간초과가 뜨면 이 방법도 종종 이용해봐야 할 것 같습니다.

---

느낀 점

확실히 지금까지 제가 풀었던 문제들에 비하면 알고리즘의 구현 등은 비교적 쉬웠다고 느꼈습니다. 그나마 좀 힘들었던 점은 제가 생각하는 바를 코드로 효율적으로 나타내는 것..? 정도였고 나머지는 별 문제가 되지 않았던 것 같습니다. 그냥 절차지향적으로 문제를 풀수도 있었겠지만, 클래스를 이용해 문제를 풀어보니 확실히 캐릭터들 간의 상호작용에 대해 더 잘 이해할 수 있었던 것 같고, 객체지향이라는 개념에 대해서도 잘 알 수 있었던 것 같습니다.

또, 이런 식으로 코드를 짜보니 진짜 제가 직접 게임을 만드는 듯한 기분이 들어 재미있었던 것 같습니다.