Algo

백준 30625 댄스타임

문제링크

회고

문제를 잘못 읽음

• 앞을 보면 같은 춤인데, 앞을 본다고 생각했고, 뒤를 보면 다른 춤인데 같이 뒤를 본다고 이해함; 그래서 경우의 수가 턱없이 안 나왔음

중복되는 계산을 밖으로 빼기

for(int i=0; i<n; i++){
    // i번째 라운드에서 틀린다고 했을 때
    // 1~ i-1라운드까지는 정답
    // i+1 ~ n 라운드까지도 정답
    int cnt = 1;
    for(int j=0; j<n; j++){
        if(i == j){
            if(danceMap[j][1] == 0) cnt *= (m-1);
        } else{
            if(danceMap[i][1] == 1) cnt *= (m-1);
        }
    }
    ans = (ans + cnt) % MOD;
}

• 아래 이중 for문을 보면 같은 작업을 매 경우마다 하고 있음. 얘를 밖으로 빼야 함
• 나의 첫 아이디어:
  • 0~ n-1번 라운드까지의 정답 수를 쫙 다 누적곱으로 구해놓기
  • 그리고 k번째 라운드에서만 틀린다고 하면 (k-1번 라운드까지 정답인 경우의 수) * (k번째 라운드 틀리는 경우의 수) * (전체가 정답인 경우의 수 / k번 라운드까지 정답인 경우의 수) 로 하면 된다고 생각함
  • arr[k-1] * (danceMap[k][1] == 1? 1: m-1) * (arr[n-1]/arr[k])
  • 그러나 예외가 존재함. M = 1일 때 → k = 1 → arr[k] = 0, arr[n-1] = 0임 따라서 0으로 나누는 이슈가 발생함
• 그래서 2번째 생각: (정답)
  • pref[]: 앞에서부터 정답인 경우를 구하기
  • sub[]: 뒤에서부터 정답인 경우를 구하기