구름톤 챌린지 3주차 학습 일기(1) 맞왜틀?

서론

새로운 한 주의 시작이다. DP 배낭 문제를 생각하며 푸니 금방 풀었지만...

Runtime Error가 발생하여 골머리를 앓았다.

DP적인 부분은 다른 블로그에서 많이 이야기할 테니, 내가 겪은 맞는데 왜 틀리지를 위주로 설명하도록 하겠다.

바로 확인해보자.

1일 차 통증(2)

문제 요약 : 통증 N과 치료제 A(x만큼 회복), B(y만큼 회복)가 무제한으로 주어질 때, 최소한의 치료제를 써서 통증을 0으로 만들 아이템의 최소 사용 개수를 출력하라. 0으로 맞추지 못할 때는 -1을 출력하여라.

 

 0으로 맞추지 못할때는 -1을 출력하여라.라는 구문 덕에 자연스럽게 DP를 통해서 구현하게 되었다.

원리는 A, B를 하나 더 쓰기 전 스트레스 상태에서 0이 될 수 있다면, 최소 값을 구하였다.

• dp[i] = min(dp[i - x] +1 + dp[i - y] +1)

 

오늘은 코드 전문부터 보여 드리고 시작하겠다.

맞는데 왜 틀려? 가 궁금하다면 넘어가도 된다.

◆코드 전문◆

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main()
{
    int N, A, B;
    cin >> N >> A >> B;

    // 메모리 오류 수정 후
    int maxSize = max(B, N);
    vector<int> dp(maxSize + 1, -1);
    dp[A] = 1, dp[B] = 1;

    for (int i = A + 1; i < B; i++)
    {
        if (dp[i - A] != -1)
        {
            dp[i] = dp[i - A] + 1;
        }
    }

    for (int i = B + 1; i <= N; i++)
    {
        if (dp[i - A] == -1 && dp[i - B] == -1)
        {
            dp[i] = -1;
        }
        else if (dp[i - A] == -1 || dp[i - B] == -1)
        {

            dp[i] = max(dp[i - A] + 1, dp[i - B] + 1);
        }
        else
        {
            dp[i] = min(dp[i - A] + 1, dp[i - B] + 1);
        }
    }

    cout << dp[N];
}

간단한 코드 설명을 하자면, dp배열을 통해 i의 통증에 필요한 최소 아이템 개수를 저장하였다.

처음 dp[A], dp[B]를 1로 초기화하고 나머지는 -1로 초기화를 하였고, 이후 A+1부터 OutofBound를 고려하여 dp[i - A]와 dp[i - B]중 작은 값을 1 더 해서 dp[i]에 넣어 주었다.

0으로 맞추지 못할 때는 -1을 출력하여라. 구문에 맞추어 불가능한 부분이 -1로 초기화되어 있으므로 if절로 dp[i - A], dp[i - B] -1인경우 알맞은 식을 통해서 dp[i]값을 정해 주었다.

이후 불가능한 값은 -1이 세팅되어 있으므로 그냥 cout<<dp[N]으로 정답을 출력해 주었다.

 

맞왜틀? (Runtime Error)(OutofBound)(어려웠던 점)

문제는 아래의 dp배열에서 일어났다.

int main()
{
    int N, A, B;
    cin >> N >> A >> B;

    // 메모리 오류 수정 전
    vector<int> dp(N + 1, -1);
    dp[A] = 1, dp[B] = 1;
    
    // 메모리 오류 수정 후
    int maxSize = max(B, N);
    vector<int> dp(maxSize + 1, -1);
    dp[A] = 1, dp[B] = 1;
}

수정 전과 수정 후의 차이를 알아보시겠나?

수정 전은 N < B 즉 통증 N보다 회복량 B가 클 수 있는 TastCase에서 문제가 발생한다.

왜냐하면 저장공간을 N+1 만큼 설정했는데 B의 경우 N+2(N+1보다 크다면)이라면 그다음 라인의 dp[B] = 1을 실행할 때 문제가 발생하여 Runtime Error가 발생했던 것이다.

이를 해결하기 위해 B와 N중 큰 값의 +1의 저장공간을 할당시켜줌으로 Runtime Error를 잡아주었다.

 

배운 점

왜 사람들이 전역변수로 MAX값을 설정하여 저장공간을 확보하는지 알게 되었다.

하지만, 장기적으로 보면 이런 데이터 관리가 C++에 중요한 만큼 이후 개발에 도움이 될 거라 생각하며 동적 할당을 멈출 수 없는 나를 보게 된다...

이런 고민 없이 동적할당으로 모든 문제를 풀 수 있도록 메모리에 대한 고찰을 더 해야겠다.

 

느낀 점

맞는데 왜 틀림?(맞왜틀)들을 경험하면서 숨겨진 TestCase를 맞추는 것이 중요하다는 걸 깨닫고 있다. 그리고 이런 것들을 글로 적게 되니 더 오래 기억되어 좋다.

또한 DP 프로그래밍에 대해 다시 기초부터 발을 들이니 기억을 되새기며 다시 배우게 된다.