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

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

6-F 그리디를 이용한 풀이

작성

192

http://boj.kr/946c8f57d8884275ae800627eb01ada3

안녕하세요 강사님.

일단은 이 문제를 보고 이분탐색 방법이 딱히 떠오르지가 않아서

그냥 마음가는대로(?) 풀었습니다.

그런데, 게시판의 반례는 다 맞는 것 같은데

제출하면 바로 틀렸다고 떠서

그냥 잘못 풀었나 보다 하고 강사님 강의를 찾아보니

이진탐색과 그리디 방법 두 가지가 있더라구요!

혹시나 해서 그리디 부분을 보니 제가 그래도 근접은 했구나 생각이 들었는데, 아무리 생각해도 어디가 틀렸는지 정확히 모르겠어가지고 잠이 안옵니다 ㅠㅠ

강사님께서는 HP를 마지막에 +1 하셨는데,

저는 그냥 처음부터 생존하기 위해 필요한 HP 1을 안고 쭉쭉 계산하는 식으로 생각했습니다.

아무래도 이 부분이 틀린것 같다고 생각은 드는데 정확히 왜 틀린건지를 모르겠습니다 ㅠㅠ 한번만 도와주세요 흑흑..

c++코딩-테스트

답변 3

큰돌

지식공유자

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

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

ㅋㅋㅋ.. ㅠ

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

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

다듬어봤습니다. 😄

#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

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

인프런 커뮤니티 질문&답변

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