[백준] 30625 댄스타임 / c++

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

30625번: 댄스타임

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second

long long n,m;
long long deno = 1'000'000'007; // 분모

vector<long long> v;
long long dp[100'005];

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m;
  
  for(long long i = 0 ; i < n ; i++ ){
    long long a,b;
    cin >> a >> b;
    v.push_back(b);
  }

  long long cnt = 0 ;

  if(v[0]==0) cnt = 1;
  else cnt = m-1;

  dp[0] = m;
  
  for(long long i = 1 ; i<n;i++){;
                           
    if(v[i]==1){
      dp[i] = dp[i-1]*(m-1);
      dp[i] += cnt;
      cnt =cnt*(m-1);
    }
    else{
      dp[i] = dp[i-1];
      dp[i] += cnt*(m-1);
    }
    dp[i] %= deno;
    cnt %= deno;         
  }

  cout << dp[n-1];
  

}

구글링 해도 아마 안나오는 것 같아서 올려둔다.

이렇게 dp 로 푸는 방법 말고

 

1. 모두 맞는 경우

2. 하나틀린 경우 

이런식으로 나눠서 푸는 방법도 존재하는데 이건 뭔가 풀면서 생각하기는 어렵다고 생각해서 패스했다. 

 

이문제에서 좀 조심해야 할 점은 그냥 int 형을 쓰면 계속 맞왜틀해서 혹시 long long 쓰면 AC 받을까 해서 돌려본 결과

int 형 범위 문제였던 것 같다. 

의외로 계속  dp 에서 정수형 범위제한을 틀리는데 조금더 조심해야 될 것 같다.