백준 10844 c++ 쉬운 계단 수

#include <iostream>
using namespace std;
 
// 초기 선언 0으로는 시작할 수 없으니
long dp[10] = {0, 1, 1, 1, 1, 1, 1, 1, 1, 1};
 
// 임시 배열을 만들고 계산 후 dp에 업데이트
void update(long* arr){
  long tmp[10];
  tmp[0] = arr[1]; // dp[0] = dp[1]
  tmp[9] = arr[8]; // dp[9] = dp[8]
  for (int i = 1; i <= 8; i++){
    tmp[i] = (arr[i - 1] + arr[i + 1]) % 1000000000; // dp[n] = dp[n-1] + dp[n+1]
  }
  for (int i = 0; i <10 ; i++){
    arr[i] = tmp[i];
  }
}
 
int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n - 1; i++){
    update(dp);
  }
  
  // 후에 합산한 결과 출력
  long ans = 0;
  for (int i = 0; i < 10; i++){
    ans += dp[i];
  }
  cout << ans % 1000000000 << endl;
}

저 연산 과정 중, 

tmp[i] = (arr[i - 1] + arr[i + 1]) % 1000000000;​

1000000000의 나머지를 구하는 부분이 있는데, 이 계산을 해도 궁극적인 답은 달라지지 않는다.

 

왜냐하면, 나중에 어차피 1000000000의 나머지를 구할 때, 배열의 합을 구하는 것이기 때문이다.

 

연산중 저 처리를 해주지 않으면, 숫자가 너무커져 dp 배열에 올바른 값이 담기지 못한다. 

 

오버플로우를 방지하기 위해 꼭 모드(%) 연산을 할 수 있는데는 해주도록 하자.