[백준] No.5557 - 1 학년 (C++)

문제

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

5557번: 1학년

 

풀이

다이나믹 프로그래밍 문제.

만약 상근이가 0이상 20이하의 수만을 안다는 제한이 없다면 메모제이션할 양이 너무나 커서 구현할 수 없었을 것이다.

상근이는 0이상 20이하의 수 만을 다룰 수 있기 때문에 다음 수와 의 +나 -결과가 범위를 벗어난다면 계산을 진행할 필요가 없었다.

 

메모이제이션 기법으로 최적화하기 위해서는 어떤 값들이 중복 계산되는지 알아야한다.

 

아래와 같은 예제가 주어졌다고 생각하자.

5

9 3 3 3 6

 

9부터 시작해서 다음 수와 +,-를 한 결과 값을 나타내보면 아래와 같다

 

6을 만드는 결과는 3가지가 존재한다.

 

 위에서 볼수 있듯이 두 번째 3을 +,-하는 과정에서 9는 (12-3)과 (6+3)에서 두 번 호출된다. 이 9는 3번째 3과 +, - 결과 값으로 12와 6을 만드는데 만약 단순히 모든 경우를 확인하는 재귀함수를 구현하였다면 같은 결과를 여러번 연산하여 비효율적이다. 따라서 우리는 이 부분을 메모이제이션 하면 최적화할 수 있다.

 

 idx위치의 수를 이전의 연산의 결과 값과 +,- 해주어 계산한 값이 0~20 경우에만 그 값을 저장해 준다.

이때 이전의 연산으로 결과로 해당 수가 몇번 등장했는지를 저장해둔 dp[0~20] 값이 이번 idx수를 계산할때 해당 수가 등장하는 경우의 수이다.

따라서 temp[num - number_set[idx]] += dp[num] 의 식이 성립하고 해당 재귀의 반복문이 끝난다면 temp값을 dp에 복사해주어 진행한다.

 

코드 (Top-bottom)

Bottom-up

재귀적으로 구현한 해당 코드를 반복문으로 수정하면 아래와 같다.

 

#include <iostream>
using namespace std;
 
int N;
int number_set[100];
long long dp[21][100] ={0,};
 
int main() { 
  cin>>N;
 
  for(int i=0; i<N ; ++i)
    cin>>number_set[i];
 
  dp[0][number_set[0]] = 1; //초기의 시작값 설정
 
  for( int num_idx=1; num_idx<N-1 ; ++num_idx)  //+,-연산에 사용되는 값
    for(int num=0; num<=20 ; ++num)
      if(dp[num_idx-1][num]>0){   //이전에 num값이 0 보다 커야 계산할 필요가 있음
        if(num - number_set[num_idx] >=0) dp[num_idx][num - number_set[num_idx]] += dp[num_idx-1][num];
        if(num + number_set[num_idx] <=20)  dp[num_idx][num + number_set[num_idx]] += dp[num_idx-1][num];
      }
 
  cout<<dp[N-2][number_set[N-1]]<<'\n';
 
  return 0;
}