DP(동적 계획법)을 풀기 위한 나만의 팁2

메모이제이션이라고 아세요?

 

 

메모이제이션 : 동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 저장해 두었다가 꺼내 쓰는 기법

 

 

 

메모이제이션은 DP를 풀기 위해서 많이 쓰는 방법 중 하나입니다.

첫 번째 팁에서 DP를 이용해 상태를 표현할 수 있다는 것을 알게 되었습니다.

특정 상태에 해당하는 값을 이미 구했다면 해당 값을 구하기 위한 연산을 할 필요가 없습니다.

메모이제이션이 그러한 역할을 하는 기법이라고 이해하면 됩니다.

 

 

메모이제이션을 사용한다면 조금 더 DP문제를 쉽게 풀 수 있습니다.

그렇다면 어떤 식으로 사용하면 될까요?

 

 

문제를 통해 알아보도록 하겠습니다.

https://www.acmicpc.net/problem/1629

1629번: 곱셈

<해당 문제는 분할 정복으로도 풀리지만 저는 메모이제이션을 이용한 DP를 사용해서 풀어보겠습니다.>

 

 

먼저 정의를 하겠습니다.

 

DP[i] : 2를 i번 곱한 상태	
D(i) : DP[i] 값을 메모이제이션하기 위한 함수

 

점화식은 다음과 같이 나옵니다.

 

if(i == 0)
     DP[i] = 1;
else if(i % 2 == 0)
     DP[i] = (DP[i / 2] * DP[i / 2]) % C;
else
     DP[i] = ((DP[i / 2] * DP[i / 2]) % C * A) % C;

 

해당 점화식에서 DP[i / 2]를 여러 번 사용하는 것을 알 수 있습니다.

DP[i / 2]를 다시 구하는 것은 비효율적입니다.

값을 다시 가져온다면 연산 횟수를 줄일 수 있습니다.

 

아래는 메모이제이션을 이용해서 답을 구한 코드입니다.

 

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define int long long
#define float double

using namespace std;

const int INF = 0x3f3f3f3f3f3f3f3fLL;

int A, B, C;
map<int,int> DP;
int D(int i)
{
     if (DP.find(i) != DP.end())       //해당 값을 구했는지 검사
          return DP[i];                //구한값이 있기 때문에 해당 값을 그래도 가져옴
    
     //값을 설정하는 단계
     if (i == 0)
          DP[i] = 1;
     else if (i % 2)
          DP[i] = ((D(i / 2) * D(i / 2))% C * A) % C;
     else
          DP[i] = (D(i / 2) * D(i / 2)) % C;
    
     return DP[i];
}
int32_t main()
{
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);
     cout.tie(NULL);

     cin >> A >> B >> C;

     cout << D(B) << endl;
}

 

저는 map을 사용하는 것을 좋아하는 편이라. map을 사용했습니다.

굳이 map을 사용하지 않고 배열을 사용해도 됩니다.

단 배열을 사용한다면 해당 값을 구했는지 검사하는 다른 과정이 필요합니다.

 

if(DP[i] == -1)     //아직 해당값이 없는상태
   return D(i);     //값을 구하는 함수실행

else                //해당값이 있는 상태
   return DP[i];    //값을 출력