문제
https://www.acmicpc.net/problem/17081
17081번: RPG Extreme
요즘 택희는 RPG 게임을 하고 있다. 던전을 헤쳐나가며 몬스터를 물리치고, 아이템을 모으고, 레벨 업을 하여 보스 몬스터를 물리치는 전형적인 RPG 게임이다. 이 게임은 N×M 2차원 그리드 위에서
www.acmicpc.net
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
| 5초 | 1024 MB | 1725 | 432 | 278 | 22.694% |
문제
문제의 정보가 너무 길고 복잡하기에 생략합니다.
간단히 요약하자면 RPG 게임을 만드는 문제였고, 그 안에 어떠한 알고리즘도 사용되지 않고 단순히 구현만 하면 되는 문제였습니다. 왜 단순 구현 문제가 브론즈나 실버도 아니고 플래티넘 2라 하면, 구현 내용이 다소 복잡하기 때문입니다.
다만 문제가 쓸데없는 말 없이 마치 기능 명세서를 보는 것처럼 간결하고 명확하게 지시가 되어 있고, 이에 따라 구현만 잘 하면 되는 문제였기에 플래티넘 2라는 난이도 치고는 훨씬 수월하게 풀 수 있습니다.
먼저 게임을 플레이하는 주인공(플레이어)(@)가 있고, 주인공이 상대하는 몬스터가 있습니다. 몬스터는 두 가지로만 나뉘는데, 보스 몬스터(M)와 일반 몬스터(&)입니다. 플레이어, 몬스터 모두 체력, 공격력, 방어력이 있습니다. 서로를 공격할 수 있으며, 이때 max(자신의 공격력 - 상대방의 방어력, 1) 만큼의 데미지를 상대방에게 입히며 해당 수치만큼 체력이 빠져나갑니다. 체력이 0 이하라면 사망합니다.
플레이어가 몬스터를 죽이면 몬스터가 갖고 있는 경험치(EXP)만큼을 획득합니다.
한편 플레이어는 최대체력이 따로 있습니다. 이는 현재 남아있는 체력을 보여주는 수치와 다른 수치입니다. 최대 체력 이상으로 주인공은 회복할 수 없습니다.
한편 플레이어는 레벨업을 할 수 있습니다. 레벨업은 현재 레벨 * 5 만큼의 경험치를 획득할 시 레벨업합니다. 예를 들어 현재 레벨이 2라면, 2*5=10만큼의 경험치를 누적해서 얻게 되면 레벨업합니다.
레벨업을 하면 최대체력이 +5가 되며, 공격력과 방어력이 각각 +2씩 증가합니다.
플레이어는 무기(W)와 방어구(A)를 장착할 수 있습니다. 무기와 방어구는 각각 자신의 공격력/방어력이 있으며, 이 수치만큼 플레이어의 공격력과 방어력을 증가시킵니다.
무기와 방어구 외에, 장신구를 추가할 수 있습니다. 장신구는 중복 없이 최대 4개까지 장착 가능하며, 모든 장신구는 각각 다른 효과를 갖고 있습니다.
- HR: 매 전투 승리 시마다 체력을 3 회복
- EX: 얻는 경험치가 1.2배, 소수점 이하는 버림
- CO: 모든 전투에서, 첫 번째 공격에서 주인공의 공격력(무기 합산)이 두 배로 적용. 즉, 모든 첫 공격에서 몬스터에게 max(1, 공격력×2 – 몬스터의 방어력)만큼의 데미지를 입힘.
이런 식으로 총 7개가 있습니다.
풀이
코드 전문
코드가 너무 길어서 깃허브 링크에 달아놨습니다. 아래 링크에서 확인할 수 있어요.
https://github.com/nx006/RPGExtreme
GitHub - nx006/RPGExtreme: 백준 RPGExtreme의 코드입니다.
백준 RPGExtreme의 코드입니다. Contribute to nx006/RPGExtreme development by creating an account on GitHub.
github.com
설명
구현 문제라서 설명할 것이 많지는 않습니다. 다만 저는 이 문제를 알고리즘 문제를 푼다기 보다는 마치 요구사항을 받은 프로그래머의 입장에서 어떻게 구현할까라는 것을 제대로 고민하면서 접근했고, 비록 게임 프로그래밍은 해본 적도 배워본 적도 없지만, 최대한 객체 지향 설계 원칙에 부합하도록 설계를 했습니다. 그래서 제가 고민했던 클래스 설계 부분 등을 공유하고자 합니다.
한편 코드를 같이 작성하면 좋은데, 그러기에는 코드가 너무 깁니다. 최대한 줄이고 줄였는데도 거의 천 줄 가까이 되는 코드이고, format을 통일한다면 천 줄 훌쩍 넘습니다. 이건 일반 백준 문제가 아니라 진짜 구현 문제기 때문에.. 그래서 그냥 코드는 최대한 줄이거나 아예 담지 않았습니다.
그림으로 간략하게 표시한 클래스 설계도입니다.
먼저 몬스터와 플레이어는 캐릭터라는 부모 클래스로부터 상속받았습니다. 둘다 공격력, 방어력, 경험치, 체력 등의 요소가 있기 때문에 동일한 속성을 갖고 있습니다.
한편 무기와 방어구 역시 각기 다른 클래스로 구현하였고, 플레이어가 이를 소유하게끔 했습니다. 그런데 사실 올바른 객체 지향 설계에 의하면 무기와 방어구도 예를 들어 Gear라는 이름의 부모 클래스를 만들어서 상속받는게 더 좋아 보입니다. 그 이유는 다음과 같습니다.
- 둘다 장착하는 아이템으로써 속성이 갖다.
- 현재는 Weapon과 Armour는 각각 공격력, 방어력을 증가해주는 속성 밖에 없으나 Weapon도 방어력을 증가시켜줄 수 있고, Armour도 공격력을 증가시켜줄 수 있기 때문입니다(후에 개발 사항이 변경된다면)
- 둘이 공유하는 어떠한 속성이 새로 생긴다면, 이를 부모 클래스에서 처리해야지 각각 클래스에서 구현한다면 코드가 중복되기 때문입니다.
그래서 다음과 같이 구현하는 게 더 좋아보입니다.
class Gear {
public:
auto getAttackPower() const -> int { return attackPower; }
auto getDefensePower() const -> int { return defensePower; }
auto setAttackPower(const int attackPower)
-> void { this->attackPower = attackPower; }
auto setDefensePower(const int defensePower)
-> void { this->defensePower = defensePower; }
protected:
int attackPower;
int defensePower;
};
class Weapon : public Gear {
Weapon(const int attack, const int defense = 0) {
setAttackPower(attack);
setDefensePower(defense);
}
};
class Armour : public Gear {
Armour(const int defense, const int attack = 0) {
setAttackPower(attack);
setDefensePower(defense);
}
};위와 같이 클래스를 구현하면, Player 클래스에서는 다음과 같이도 장착 가능합니다.
class Player : public Character {
public:
template <class T> requires std::is_base_of_v<Gear, T>
void setGear(const T& gear) { gears.emplace_back(gear); }
private:
std::vector<Gear> gears;
};setGear 함수는 클래스 템플릿 T의 gear를 받아서 이를 gears라는 벡터에 장착합니다. 과연 이게 옳은 방법인지는 모르겠는데, 하나의 옵션은 될 것 같습니다.
저같은 경우는 C++20부터 새로 등장한 템플릿 컨셉트를 적극적으로 사용하는 편이라서, 템플릿 T를 기어 클래스로부터 상속받는 지를 확인하는 std::is_base_of_v 컨셉트를 적용했습니다.
물론 저렇게 하면 이제 장비는 하나씩 장착해야 하니깐, 종류에 따라서 갯수를 제한하는 코드는 만들어야 할 거예요.
그래서 풀 때 저 생각을 하긴 했는데, 일단 이 문제는 추후 확장 가능성을 생각하지 않아도 되고, 사실 복잡하게 상속하다가 틀리면 디버깅이 어렵겠다는 생각이 들어서 굳이 저렇게 구현하지는 않았어요.
한편 장신구(ORNAMENT)는 enum class로 처리했습니다. 장신구는 클래스로 만들기에는 맞지 않아보여요. 7개의 장신구가 각기 다른 효과를 갖고 있고 이를 공유하는 속성도 없어요. 그래서 그냥 플레이어가 갖고 있는지만 확인하기 위해 std::unordered_set 으로 저장했고, 매 상황마다 이를 조건문으로 확인하여 ORNAMENT의 효과를 보게끔 했습니다.
그런데 예를 들어 공력력 2배, 또는 경험치 1.2배 등의 단순 수치 강화의 경우 조건문 말고 해쉬 테이블로 설계하였다면 조건문을 더 줄일 수도 있었을 것 같네요.
한편 여기서 작은 해프닝이 있었는데... 저는 처음에 장신구를 accessory라고 이름을 짓고 함수를 만들고 있었는데, 문제 읽다보니깐 장신구를 나타내는 기호로 알파벳 O를 사용하더군요. 그래서 O가 뭘까 생각하다가 그제서야 장신구를 ORNAMENT라고 해야 하는 것을 알았습니다.. 그래서 코드에는 accessory와 ornament의 이름이 혼용되어 있어요.. 이건 반드시 리팩토링해야 하는 중요한 문제지만 사실 저걸 알아차린 시점에서 이미 지쳐버려서.. 그냥 그대로 혼용한 채로 완성했습니다.
플레이어는 다음과 같이 무기와 방어구, 악세서리 정보를 지니게끔 했습니다.
class Player : public Character {
public:
auto setArmour(const Armour& armour) { this->armour = std::make_unique<Armour>(armour); }
auto setWeapon(const Weapon& weapon) { this->weapon = std::make_unique<Weapon>(weapon); }
int get_defense() const override {
if (armour.get() == nullptr) return defense;
return defense + armour->get_defence();
}
int get_attack() const override {
if (weapon.get() == nullptr) return attack;
return attack + weapon->get_attack();
}
auto get_pure_attack() const { return attack; }
auto get_pure_defense() const { return defense; }
auto get_weapon_attack() const {
if (weapon.get() == nullptr) return 0;
return weapon->get_attack();
}
auto get_armour_defense() const {
if (armour.get() == nullptr) return 0;
return armour->get_defence();
}
private:
std::unique_ptr<Armour> armour;
std::unique_ptr<Weapon> weapon;
std::unordered_set<ACCESSORY_LIST> accessories;
};armour, weapon은 모두 단 하나 밖에 장착하지 못 하기에, 포인터로 동적할당시켰습니다. 악세서리는 중복을 제거하기 위해 집합으로 처리하였고, std::set보다는 O(1)의 시간 복잡도로 원소를 찾을 수 있는 std::unordered_set을 사용했습니다.
한편 굳이 weapon, armour를 integer로 그 공격력 증가, 방어력 증가 수치만 표시하지 않은 이유는, 사실 이 문제를 풀 때는 그렇게 하는게 더 간편하긴 하나 객체 지향적 관점에서 보면 따로 클래스로 분리하는게 더 나아 보였습니다.
그리고 armour와 weapon은 다른 객체가 자원을 공유할 이유가 없기에 shared_ptr대신 unique_ptr을 사용했습니다.
한편 World는 Map 정보에 관한 클래스입니다. 몬스터는 필드 위의 객체이고, World에 종속되어 있는 객체이기에 World가 관리를 합니다.
마지막으로 RPGExtreme 클래스가 Player와 World를 가지면서, 메인 함수에선 RPGExtreme만을 사용합니다.
Player는 World에 종속되지 않아서 RPGExtreme이 관리하게 두었습니다. 그래서 Player의 Position도 RPGExtreme이 관리합니다.
사실 RPGExtreme은 어케 하다보니깐 조금 깔끔하게 구현하는데 실패한 클래스가 되었습니다. 그 이유는 RPGExtreme 클래스의 함수들이 절차 지향적으로 묶여 있어요. 순서에 의해 서로 종속적으로 묶여 있다 보니 main에서 사실 이 함수들을 따로따로 쓰지 못하고, 그냥 하나의 함수처럼 써야 해요. 백준이어서 그냥 이렇게 구현했지만 실제로 이렇게 서로 종속적이고 절차지향적으로 작성하면 안 될 것 같습니다..
함수 오버로딩/오버라이딩 시 어려움
제가 겪었던 어려움이고, 제가 아직 C++에 미숙하여서 정확히 어떤 원리로 오버로딩/오버라이딩이 동작하는 건지 모르겠어요. 근데 제가 겪었던 문제는, 동일한 코드를 하나는 C++20로, 하나는 C++20(Clang) 옵션으로 제출했을 때 전자는 틀리고 후자는 맞았다는 거예요. 완전히 동일한 코드로요.
단순히 컴파일러만 바뀌었을 뿐인데, 이상하지 않나요? 저도 아직 정확한 이유를 모르겠습니다. 그런데 제가 생각했을 때 가장 유력한 이유는 GCC와 Clang이 제 코드를 다르게 해석했다고 추측합니다. 저는 MSVC 컴파일러를 이용했는데 이 컴파일러가 Clang과 같은 방식으로 제 코드를 컴파일한 반면, 아마 백준 컴파일러는 GCC를 사용하지 않을까 싶은데, 이 차이 때문인 것 같아요. 백준이 어떤 컴파일러를 쓰는지 모르니 여기서 GCC란 백준 컴파일러를 의미한다고 할게요.
GCC와 Clang이 다르게 해석한 가장 유력한 후보는 아마 함수 오버로딩, 오버라이딩 때문이 아닐까 싶어요.
정확하진 않으니 그냥 제 뇌피셜을 쭉 써볼게요.
먼저 용어정리부터 하고 가자면,
- 오버로딩은 똑같은 이름의, 그러나 다른 형태의 함수를 의미합니다. 예를 들어 void func(); void func(const int N); 위에 func는 이름은 같은데, 생김새가 다릅니다. 그러니깐 이 둘은 본질적으론 아예 다른 함수고, 컴파일러도 이를 다른 함수로 인식합니다.
- 오버라이딩은 부모 클래스의 함수를 다시 쓰는 것을 의미합니다. 그러니깐 오버라이딩 함수는 기존 함수를 대체하는 것이고, 그렇기에 형태가 똑같아야 하며, 오버라이딩을 한 순간 기존 함수는 사용하지 못 합니다(super 처럼 부모 키워드를 가져오지 않는 한)
- C++는 기본적으로 다형성을 지원하는 언어기에 이런 부분에 대해서 잘 처리를 해주었는데, 그럼에도 기본 인자 등과 엮여서 강력한 모호성을 발생시키기도 합니다. 예를 들어 void func(); void func(const int N = 0); 위와 같이 함수가 있다면, func(1)은 정확히 특정은 되지만 func(); 라 호출하면 이게 어떤 함수인지를 알 수 없습니다. 이런 걸 모호성이라고 합니다.
- 모던 C++에서는 이런 모호성을 방지하기 위해, 오버라이딩의 경우 override 키워드를 붙이게끔 합니다. 오버라이딩 당하는 부모 함수는 virtual 키워드로 가상 함수로 만들 수도 있고, 아예 순수 가상 함수(pure virtual function)으로 만들 수도 있구요.
- 그런데 내가 만약 부모 클래스에서 함수를 호출하고 싶은데, 자식 클래스에 오버로드된 함수가 있다면 여기서 모호성이 발생할 수 있어요. 그때는 밑에 써놓은 대로 using 키워드를 사용할 수 있습니다.
같은 이름(attack_opponent) 함수를 오버로딩, 오버라이딩을 둘다 동시에 했는데, 그러다보니깐 MSVC에서는 잡히지 않는 모호성이 생기더라구요.
그래서 GCC랑 MSVC랑 제 코드를 해석하는 방식이 다른 것 같아요. 저는 MSVC에서 이 함수를 호출하기를 원했고 MSVC에서는 실제로 그 함수를 호출해주었지만, GCC 컴파일러는 제가 의도하지 않았던 다른 함수를 호출한 것 같아요. 반면에 Clang은 MSVC의 의도대로 호출을 해준 것 같구요.
근데 어디에서 문제가 생겼는지는 모르겠습니다..
한편 간단한 상속 관계에서 함수 오버로딩의 예를 보자면 아래와 같아요.
class Character {
public:
// 상대방을 공격함. 이때 입힌 damage는 max(1, 내 공격력 - 상대방 방어력)
virtual void attack_opponent(Character& opponent) {
opponent.get_damaged_health(std::max(1, this->get_attack() - opponent.get_defense()));
}
}
class Monster : public Character {
public:
using Character::attack_opponent;
/// <summary>
/// opponent에게 damage만큼의 피해를 가함
/// 이때 가한 데미지 - opponent의 방어력 만큼 데미지가 차감됨
/// 단 음(-)의 데미지를 가할 수 없으므로, 음의 수라면 1의 데미지가 됨
/// 즉 공격력 < 상대방 방어력이라면 1만큼 데미지가 들어감
/// </summary>
/// <param name="opponent">공격하는 상대방</param>
/// <param name="damage">가하는 데미지</param>
void attack_opponent(Character& opponent, const int damage) {
opponent.set_health(opponent.get_health() - std::max(1, damage - opponent.get_defense()));
}
}
class Player : public Character {
public:
using Character::attack_opponent;
/// <summary>
/// opponent에게 damage만큼의 피해를 가함
/// 이때 가한 데미지 - opponent의 방어력 만큼 데미지가 차감됨
/// 단 음(-)의 데미지를 가할 수 없으므로, 음의 수라면 1의 데미지가 됨
/// 즉 공격력 < 상대방 방어력이라면 1만큼 데미지가 들어감
/// </summary>
/// <param name="opponent">공격하는 상대방</param>
/// <param name="damage">가하는 데미지, 0이 될 수도 있음</param>
void attack_opponent(Character& opponent, const int damage) {
opponent.set_health(opponent.get_health() - std::max(1, damage - opponent.get_defense()));
}
}사실 코드를 리뷰하다가 monster와 player의 attack_opponent함수가 같아졌다는 것을 알게 되었는데, 원래 개발 과정에서는 최소 공격력이 0이나 1이냐 이런 차이가 있었습니다. 추후에 바뀌었는데, 그래서 위에 코드는 사실 attack_opponent를 Character 클래스로 넣는게 더 좋아보입니다.
C++에서 부모 클래스의 함수가 자식 클래스에서 오버로드되었을 때, 자식 클래스에서 원래의 부모 클래스를 호출하진 못 합니다. 컴파일러에서는 자식 클래스의 attack_opponent 함수까지만 해석하고, 만약 attack_opponet(monster); 이렇게 쓰면, 컴파일러는 attack_opponent 함수를 보고 이것이 2개 인자를 받아야 한다고 에러를 띄울 겁니다. 컴파일러는 기본적으로 최대한 자식 클래스 내부까지만 해석하지, 부모 클래스까지 올라가서 해석하려 들지 않습니다.
컴파일러에게 해당 형태를 가지는 함수가 있다고 알려주려면 using ParentClass::func; 를 쓰면 됩니다. 그러면 부모클래스에서 해당 함수를 찾아서 그것까지 오버로드된 함수로 찾아볼 겁니다. 팁이에요.
실패하였을 시 주의사항들
다음 사항들을 주의깊게 살펴보아야 합니다. 저도 초반에는 특히 몬스터가 체력이 0이 되어 사망했는데도 마지막 한 방을 더 때려서, 그래서 틀렸습니다. 차근차근 종이에 써가면서 디버그하다가 발견했습니다.
- 어느 한 쪽, 특히 몬스터가 사망했을 경우(몬스터의 체력이 0 이하이면) 몬스터는 플레이어를 공격하지 않습니다. 아래는 이 내용을 지침삼아 구현한 코드입니다.
/// <summary>
/// Fight with opponent
/// </summary>
/// <param name="monster">opponent that fight with player</param>
/// <param name="courage">multiply the player's attack skill once</param>
void fight(Monster& monster, const int courage) {
player.attack_opponent(monster, courage * player.get_attack());
// 만약 플레이어의 첫 공격에도 몬스터가 살아있다면,
// 서로 일합식 주고 받음
while (monster.is_alive() && player.is_alive()) {
monster.attack_opponent(player);
if (!player.is_alive()) break;
player.attack_opponent(monster);
}
}위에서 반복문 안에 if (!player.is_alive()) break; 이 부분이 있어야 합니다. 그리고
/// <summary>
/// Fight with opponent, First Attack by boss equals monsterAttack(only once)
/// then next equal as original boss attack
/// </summary>
/// <param name="monster">opponent that fight with player</param>
/// <param name="courage">multiply the player's attack skill once</param>
/// <param name="monsterAttack">equals first boss attack</param>
void fight(Monster& monster, const int courage, const int monsterAttack) {
player.attack_opponent(monster, courage * player.get_attack());
// 만약 플레이어의 첫 공격에도 몬스터가 살아있다면 몬스터가 공격함
if (monsterAttack != 0 && monster.is_alive()) {
// monsterAttack == 0 이면 몬스터는 공격하지 않고 턴을 넘김
monster.attack_opponent(player);
}
// 보스의 첫 공격에도 플레이어가 살아있다면 서로 한 합 식 주고 받음
while (player.is_alive() && monster.is_alive()) {
player.attack_opponent(monster);
if (!monster.is_alive()) break;
monster.attack_opponent(player);
}
}여기서도 반복문 안에서 if (!monster.is_alive()) break; 이 부분에서 몬스터가 사망했다면 바로 반복문을 깨고 탈출해야 합니다. 사실 첫 번째 fight문같은 경우 어차피 플레이어 사망 시 몬스터를 한 대 더 때린다고 해도 백준 푸는데 별 문제는 안 되는데, 밑에 fight 함수의 경우 저렇게 안 하면 예제 2에서 틀립니다. 몬스터가 이미 사망했는데도 한 대를 더 때려서요.
한편 첫 합의 경우 ORNAMENT의 효과를 반영하기 위해서 반복문 밖에 빼놨습니다. 반복문 안에 조건문이 들어가게 되면 성능 상 이슈가 있을 것 같아서였는데, 앞서 말한대로 공격력 증가 계수같은 건 해쉬 테이블로 빼놨으면 성능 저하 없이도 더 간결하게 구현 가능할 것 같습니다.
- 체력은 음수가 되지 않습니다.
- 가시함정는 밟아도 사라지지 않습니다. 특히 REINCARNATION 시에도 사라지지 않아야 합니다.
- REINCARNATION 시 싸우던 몬스터의 체력을 풀로 채워야 합니다.
- 새로운 무기, 방어구가 나오면, 무조건 이를 장착해야 합니다. 심지어 스탯이 낮더라도 장착해야 합니다.
- REINCARNATION 시 RE를 무조건 제거해줘야 합니다.
- 데미지는 max(1, damage - opponent.defense()) 만큼 들어갑니다. 즉 내 공격력 - 상대방 방어력 만큼 들어가는데, 이게 1 이하라면 1씩은 무조건 들어갑니다.
- 그런데 이 조건때문에 다음 조건을 놓칠 수가 있는데, 만약 HU 를 가지고 있다면 보스의 첫 공격은 데미지가 0입니다. 저같은 경우 이에 대한 따른 함수를 오버로딩해서 사용했는데, 계속 틀리니깐 이게 문제인가 싶어 그냥 HU를 가지고 있다면, 플레이어가 연속으로 두 번 때리게 했습니다.
- 이건 사실 성능의 관점인데, 반복문 안에 조건문이 많으면 좋지 않습니다. 그래서 일부러 특수한 케이스(첫 번째 공격)를 반복문 전에 빼놓은 겁니다. 만약 반복문 내에서 매번 첫 번째 공격인지를 검사한다면 성능적 측면에서 그리 좋진 않습니다.
마지막으로 위에 사항들을 전부 다 지켰음에도 틀린다면.. 그리고 자신이 정말 왜 틀렸는지 모르겠다면... 한 번 저처럼 컴파일러를 바꾸어보십시오.. 완전히 똑같은 코드인데 맞았습니다..
사실 그래서 조금 찝찝한 문제이긴 합니다. 뭐 그래도 맞았으니깐 된 거고, 결국 테스트 과정에서 잘 작동했으니깐 잘 풀린 문제라고 생각합니다.
총평 및 후기, 배운 점
플래티넘 2는 지금껏 제가 푼 문제 중 가장 높은 티어의 문제였습니다. 그럼에도 불구하고 단순 구현 문제여서 도전하기에 좋은 것 같습니다. 저도 제 티어는 실버4이지만 문제 자체는 하루종일 코딩하고, 다음날 디버깅하면서 수월하게 풀었습니다. 만약 플래에 걸맞는 다른 알고리즘들이 들어갔다면 자력으로는 절때 못 풀었을 것 같아요.
참고로 이 문제는 2019년 연세대학교 프로그래밍 경진대회에서 출제된 문제고, 해당 대회의 제한 시간은 5시간이었다고 합니다. 동시에 해당 대회에서 이 문제를 해결하고 나온 사람들은 대부분 이 문제를 3시간 내에 풀었다고 합니다.
저는 이거 푸는데 꼬박 하루를 썼는데, 진짜 대단한 것 같습니다…
