글 읽기 - bottom-up DP에서 모듈러 연산의 위치

colorxxx 5년 전 0

이 알고리즘은 2차원 배열을 사용하여

d[L][N] 길이가 L이고 끝에자리가 N로 끝나는 오르막의 수로 정의했습니다.

소스를 보면 23번쨰줄에서 dp배열에 모듈러연산을 해서 넣는데

연산중에 모듈러연산 한 결과를 넣으면 다음 dp테이블을 참조할떄

모듈러 된 연산값이 dp테이블에 들어갑니다.

즉 오르막의 수가 나눠진 채로 대입이 되게 되어서

최종결과가 다르게 나오지 않을까요?

그런데 저게 없으면 틀리네요 ㅠ 왜 23번쨰 줄이 필요한지 모르겠습니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

long long mod = 10007;
long long d[1001][10];//이거 int로 바꿔보기 

int main() {
	
	int n = 0;
	cin >> n;

	for (int i = 0; i <= 9; i++)
		d[1][i] = 1; //길이가 1이고 끝에자리가 i로 끝나는 오르막 수

	for(int i=2;i<=n;i++)//길이가 i이고
		for (int j = 0; j <= 9; j++) //끝의자리는 0~9가 가능하다
			for (int k = 0; k <= j; k++) { //다 더해줘야함.
				d[i][j] += d[i - 1][j-k];
				d[i][j] %= mod;
			
			}

	

	long long ans = 0;
	for (int i = 0; i <= 9; i++)
		ans += d[n][i];

	ans %= mod;

	cout << ans;

		
}


//23번쨰줄 %= mod 왜해주는거지?ㅠㅠ모르겠다

Green55 5년 전 0

모듈러 연산의 성질에 대해 공부해 보세요

두 수의 합의 모듈러는, 각 수의 모듈러를 더한 모듈러와 같습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

bottom-up DP에서 모듈러 연산의 위치

colorxxx 5년 전 0

Green55 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말