6-F 그리디 질문입니다.

와 호은님... 드뎌 고쳤습니다...

저 징짜 열심히 했어요...

ㅋㅋㅋ.. ㅠ

사실 반례를 처음에는 찾으려다가 잘 안되가지고..

이럴 때 저는 그냥 코드를 다듬으면서 이렇게 해보면 어떨까? 하면서 고쳐나가가거든요.

다듬어봤습니다. 😄

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int DungeonSize; // 던전 방의 수
    long long Atk; // 용사의 초기 공격력
    cin >> DungeonSize >> Atk;

    long long MaxHp = 1; // 용사의 최대 체력을 가능한 최소값으로 초기화
    long long CurHp = 1; // 현재 체력, 최대 체력과 동일하게 초기화
    long long MinHpNeeded = 1; // 용사가 살아남기 위해 필요한 최소 체력을 추적

    for (int i = 0; i < DungeonSize; ++i)
    {
        int t;
        long long a, h;
        cin >> t >> a >> h; // 각 방의 정보 입력

        if (t == 1) // 몬스터 방인 경우
        {
            long long attacksNeededByWarrior = (h + Atk - 1) / Atk; // 용사가 몬스터를 쓰러뜨리기 위해 필요한 공격 횟수
            long long attacksNeededByMonster = (CurHp + a - 1) / a; // 몬스터가 용사를 쓰러뜨리기 위해 필요한 공격 횟수

            // 용사가 몬스터를 쓰러뜨리는데 필요한 공격 횟수가 몬스터가 용사를 쓰러뜨리는데 필요한 횟수보다 많을 경우
            if (attacksNeededByWarrior > attacksNeededByMonster)
            {
                long long additionalHpNeeded = (attacksNeededByWarrior - 1) * a - CurHp + 1;
                MinHpNeeded += additionalHpNeeded; // 필요한 최소 체력 업데이트
                CurHp += additionalHpNeeded; // 추가로 필요한 체력만큼 현재 체력 증가
            }
            
            CurHp -= (attacksNeededByWarrior - 1) * a; // 몬스터 공격으로 인한 체력 감소
        }
        else if (t == 2) // 포션 방인 경우
        {
            CurHp = min(MinHpNeeded, CurHp + h); // 체력을 h만큼 회복하지만 MinHpNeeded를 초과하지 않음
            Atk += a; // 공격력을 a만큼 증가
        }

        CurHp = max(CurHp, 1LL); // CurHp가 1 미만으로 떨어지지 않도록 보장
    }

    cout << MinHpNeeded << '\n'; // 필요한 최소 체력 출력

    return 0;
}

이렇게 고쳐보시겠어요? 주석도 달아놓았습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요 호은님 ㅎㅎ

하.. 이거 애매하네요... ㅠ

반례 일 것 같다는 것 죄다 넣어보고 있는데 다 맞다고 뜨고...(많이 해봤습니다... ㅠ)

제가 반례찾으면 다시 답변 드리겠습니다 ㅠㅠ

죄송합니다..

고민해주셔서 감사합니다 강사님 ㅠㅠ 밤늦게까지...

저도 너무 계속 오답이 떠가지고 고민이 많았는데 해결해주셔서 다시 감사드립니다 ㅠㅠ

풀이는 맞는 것 같은데 반례가 안찾아질때는 한번 코드를 다듬어보며 고쳐나가라는 말씀 새겨듣겠습니다 다시 한 번 감사드립니다..!!!

http://boj.kr/6f56422b3d444a8989b14eb5d79b06fd

강사님 소스 참고해서 고치니 드뎌 정답이 떳습니다 ㅠㅠ

• 계속 여러가지를 시도해 봤는데.. 결론적으로는 자료형과 CurHp -= RequiredHp;이 부분이 문제였던 것 같습니다.. RequiredHp에는 1을 고려해서 +1이 되어있어서,, 그대로 CurHp에 뺄셈할 경우 이상한 답이 나오는 경우가.. 있었나봅니다 ㅠㅠ 반례로 안잡혀서 몰랐네요...

   

위 부분을 참고해서 원래 소스를 고치니

http://boj.kr/876d5fd732d04beea3150e8d6a374fc7

이렇게도 정답이 되네요 .!!! 다시 한 번 감사합니다ㅋㅋㅋㅋ