[프로그래머스] [PCCP 기출문제] 1번 / 붕대 감기(C++)

안녕하세요! 오늘은 프로그래머스의 코딩테스트 문제 중 하나인 "분대 감기 게임" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제는 게임 캐릭터의 체력을 관리하고 몬스터와의 전투에서 생존 여부를 판단하는 문제입니다. 이 문제를 푸는 과정을 자세히 알아보겠습니다.

 

문제링크 : 

https://school.programmers.co.kr/learn/courses/30/lessons/250137?language=cpp

프로그래머스

문제 개요

주어진 게임에서는 붕대 감기라는 기술을 사용할 수 있습니다. 이 기술은 다음과 같은 규칙으로 동작합니다.

• 붕대 감기를 시전하면 t초 동안 붕대를 감으면서 1초마다 x만큼의 체력을 회복합니다.
• t초 연속으로 붕대를 감는 데 성공한다면 y만큼의 체력을 추가로 회복합니다.

게임 캐릭터는 최대 체력이 있으며, 현재 체력이 최대 체력보다 커지는 것은 불가능합니다. 또한, 몬스터의 공격을 받으면 정해진 피해량만큼 현재 체력이 줄어들며, 체력이 0 이하가 되면 캐릭터가 죽습니다.

문제의 입력으로는 붕대 감기 기술의 정보, 캐릭터가 가진 최대 체력, 몬스터의 공격 패턴이 주어집니다. 이때, 캐릭터가 끝까지 생존할 수 있는지를 판단하고, 생존할 경우 남은 체력을 반환해야 합니다.

문제 해결 방법

이 문제를 해결하기 위해서는 다음과 같은 단계를 따라갑니다.

1. 몬스터의 공격 시간과 피해량을 기록합니다. 이를 위해 attackTime이라는 맵을 사용합니다.
2. 시뮬레이션을 통해 게임을 진행합니다. 0부터 마지막 공격 시간까지 시간을 증가시키면서 다음을 수행합니다.
3. 게임 종료 시점에서 캐릭터의 남은 체력을 반환합니다.

코드 구현

문제를 해결하기 위한 코드는 다음과 같습니다. C++을 사용하여 작성되었으며, 주석을 통해 코드의 각 부분을 설명하였습니다.

#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

map<int, int> attackTime;

int solution(vector<int> bandage, int health, vector<vector<int>> attacks) {
    int answer = 0;
    int lastTime = 0;
    int count = 0;

    // 몬스터의 공격 시간과 피해량을 저장하는 attackTime 맵을 초기화합니다.
    for (int i = 0; i < attacks.size(); i++) {
        attackTime[attacks[i][0]] = attacks[i][1];

        // 마지막 공격 시간을 저장합니다.
        if (i == (attacks.size() - 1)) {
            lastTime = attacks[i][0];
        }
    }

    answer = health;

    // 0부터 마지막 공격 시간까지 시뮬레이션을 진행합니다.
    for (int i = 0; i <= lastTime; i++) {
        if (attackTime[i] != 0) {
            answer -= attackTime[i];
            count = 0;

            // 현재 체력이 0 이하면 게임 종료
            if (answer <= 0) {
                answer = -1;
                break;
            }
        } else {
            // 몬스터의 공격이 없는 경우, 붕대 감기 기술을 사용합니다.
            if (answer <= health && count < bandage[0]) {
                answer += bandage[1];
                count++;

                // 연속으로 기술을 사용하면 추가 회복량을 적용합니다.
                if (count >= bandage[0]) {
                    answer += bandage[2];
                    count = 0;
                }
            }
        }

        // 현재 체력이 최대 체력을 넘어가면 최대 체력으로 설정합니다.
        if (answer >= health) {
            answer = health;
        }
    }

    return answer;
}

결과 및 시간 복잡도

주어진 예제에 대한 결과를 확인하면 문제를 정확하게 해결하는 것을 확인할 수 있습니다. 이 알고리즘의 시간 복잡도는 입력으로 주어진 attacks 배열의 길이에 비례하며, 모든 시간 단계에 대해 게임을 시뮬레이션하므로 최악의 경우에도 attacks 배열의 길이만큼의 연산을 수행합니다. 따라서 시간 복잡도는 O(N)이며, N은 attacks 배열의 길이입니다.