글 읽기 - 9341 ZZ 점화식 힌트 주실수있나요?

dlftls38 4년 전 1

Ries 마법의 수퍼마리오 님의 블로그를 보며 공부하고있습니다.

http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=221383409543&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postView

이 블로그에서 동적계획법 DP문제를 행렬 곱셈을 통해 n이 상당히 클 때 푸는 법을 공부하고있습니다.

저 사이트에 있는 피보나치 수3, 정수수열, 본대산책, 합 구하기 등등 다 풀었는데

마지막 ZZ문제를 못풀고있습니다. 합 구하기 문제와 비슷하다고 하셨는데 상당히 비슷함을 느끼고 있습니다.

아직 점화식을 구해 행렬에 넣는것이 미숙해 이 문제에서 헤매고있습니다.

문제에서 주어진 점화식 말고는 아무리해도 못구하겠습니다.

합 구하기 문제와 같은 점화식 방식으로하면 n마다 더해야하는 값이 달라져서 행렬에 어떤 점화식으로 넣어야 할지 모르겠습니다..

점화식을 어떻게 구해야할까요??!!!

코드는 점화식부분을 못채웠습니다.. SIZE도 어떻게 정할지 모르겠고..ㅠㅠ

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <limits.h>
#include <functional>
#include <math.h>
#include <fstream>
#define INF 987654321

using namespace std;
const int MOD =  1000000009;

vector<vector<long long>> matrix_mul(vector<vector<long long>>& a, vector<vector<long long>>& b){
	int i,j,k;
	int n = a.size();
	vector<vector<long long>> c(n, vector<long long>(n));
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			for (k = 0; k < n; k++)
			{
				c[i][k] += a[i][j] * b[j][k];
				c[i][k] %= MOD;
			}
		}
	}
	return c;
}
int main(){
	int tc;
	scanf("%d",&tc);
	while(tc--){
		int i,j;
		int a,b,c,d;
		scanf("%d%d%d%d", &a,&b,&c,&d);
		
		int SIZE = c+3;
		vector<vector<long long>> ans(SIZE, vector<long long>(SIZE,0));
		vector<vector<long long>> arr(SIZE, vector<long long>(SIZE,0));
		
		for(i = 0; i < SIZE; i++){
			ans[i][i] = 1;	                // 단위 행렬 
		}
		for(int i = 0; i < SIZE; i++){
			for(int j = 0; j < SIZE - i ; j++){  //점화식 넣는 곳  
				arr[i+j][j]=1;  
			}
		}
		while (d > 0)
		{
			if (d % 2 == 1)
			{
				ans = matrix_mul(ans, arr);
			}
			arr = matrix_mul(arr, arr);
			d /= 2;
		}
		
		printf("\n");
		int res=0; 
		for(i = 0; i < SIZE; i++){
			for(j = 0; j < SIZE ; j++){
				printf("%d ",ans[i][j]);
			}
			printf("\n");
		}
		printf("\n");
	}
}

sait2000 4년 전 1

저는 행렬로 안 풀어서 모르겠지만 ZZ(i, k + 1) = ZZ(i, k) + ZZ(i - 1, k + 1)로 식을 세울 수 있지 않을까요

dlftls38 4년 전 0

그 점화식을 이용하고 싶은데 행렬에 어떻게 옮겨야할지 모르겠습니다...ㅠㅠ

합 구하기 문제의 경우에는 n이나 k 달라지더라도 모두 고정적으로 점화식 + 1을 더하는 것이었고

이 문제는 고정적으로 자신의 위치의 위와 왼쪽 값을 더하는 것이지만, 제가 그린 위 그림에서는 c가 0인 경우가 있지만 문제에서는 c>=1이라서

그럼 만약 c가 1일때는 왼쪽 값이 없어서 행렬에 어떻게 옮겨야 할지 모르겠습니다

왠지 행렬곱셈에 아직 익숙치 않아 잘못 생각하고 있는 느낌이 드는데 모르겠습니다..

sait2000 4년 전 1

ZZ(0, n-1) ZZ(0, n) ZZ(1, n) ZZ(2, n) ... 을 잘 조합해서 ZZ(0, n) ZZ(0, n+1) ZZ(1, n+1) ZZ(2, n+1) ...을 만들 수 있을까요?

sait2000 4년 전 0

아 c가 1이면 어떡하냐는 말씀이시군요. 그냥 점화식이 성립하게 만드는 값을 주면 되는데요 ZZ(0, 0) = b - a, ZZ(n, 0) = 0 (n > 0)

dlftls38 4년 전 0

생각한다고 떠오르지 않고 모르는 영역임을 인정하고 포기하기 직전 마지막으로 점화식을 세워봤습니다.

왜 합 구하기와 비슷하다고 했는지 알았습니다

점화식이 똑같이 나왔습니다.

하지만 저대로 대입하면 답은 나오지 않습니다

아마 c, d만 이용하고 a,b를 사용하지 않아서 그런 것 같은데 a,b를 초기값으로 어딘가에 줘야할 것 같은데

제 생각에는 당연히 저 ZZ(0,n) 부분일 것 같습니다. 피보나치 형식이기에 값을 구해보았지만 어디에 대입해야 할지 모르겠습니다.ㅠㅠ

제발 도와주세요 오늘하루 이문제만 파고있는데.. 익숙치 않은 영역이라 답으로 도달하는데 도움이 필요합니다

저 점화식이 맞다면 코드는 다 짰습니다 a,b를 어떻게 이용해야 하나요!??!?!?!

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <limits.h>
#include <functional>
#include <math.h>
#include <fstream>
#define INF 987654321

using namespace std;
const int MOD =  1000000009;

vector<vector<long long>> matrix_mul(vector<vector<long long>>& a, vector<vector<long long>>& b){
	int i,j,k;
	int n = a.size();
	vector<vector<long long>> c(n, vector<long long>(n));
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			for (k = 0; k < n; k++)
			{
				c[i][k] += a[i][j] * b[j][k];
				c[i][k] %= MOD;
			}
		}
	}
	return c;
}
int main(){
	int tc;
	scanf("%d",&tc);
	while(tc--){
		int i,j;
		int a,b,c,d;
		scanf("%d%d%d%d", &a,&b,&c,&d);
		
		int SIZE = c+1;
		vector<vector<long long>> ans(SIZE, vector<long long>(SIZE,0));
		vector<vector<long long>> arr(SIZE, vector<long long>(SIZE,0));
		
		for(i = 0; i < SIZE; i++){
			ans[i][i] = 1;	                // 단위 행렬 
		}
		for(i = 0; i < SIZE; i++){
			for(j=0;j<i+1;j++){
				arr[i][j]=1;                 // 점화식  
			}
		}
        
        
        
		// ↓ 피보나치
		vector<vector<long long>> ans2(2, vector<long long>(2,0));
		vector<vector<long long>> arr2(2, vector<long long>(2,0));
		ans2[0][0]=1;
		ans2[1][1]=1;
		
		arr2[0][0]=1;
		arr2[0][1]=1;
		arr2[1][0]=1;
		int dd=d;
		while (dd > 0)
		{
			if (dd % 2 == 1)
			{
				ans2 = matrix_mul(ans2, arr2);
			}
			arr2 = matrix_mul(arr2, arr2);
			dd /= 2;
		}
		
		printf("\nfibonacci");
		printf("\n");
		for(i=0;i<2;i++){
			for(j=0;j<2;j++){
				printf("%d ",ans2[i][j]);
			}
			printf("\n");
		}
		printf("\n");
		// ↑ 여기까지 피보나치
        
        
        
        
		while (d > 0)
		{
			if (d % 2 == 1)
			{
				ans = matrix_mul(ans, arr);
			}
			arr = matrix_mul(arr, arr);
			d /= 2;
		}
		printf("\nans");
		printf("\n");
		int res=0; 
		for(i = 0; i < SIZE; i++){
			for(j = 0; j < SIZE ; j++){
				printf("%d ",ans[i][j]);
			}
			printf("\n");
		}
		printf("\n-------------------\n");
	}
}

sait2000 4년 전 1

점화식을 조금 더 잘 세우셔야 합니다. 지금 ZZ(0, n)이 ZZ(0, n+1)로 바뀌어야 하는데 안 바뀌잖아요. 제가 위 댓글에 쓴 것처럼 ZZ(0, n - 1), ZZ(0, n) ZZ(1, n) ZZ(2, n)...으로 식을 세워보세요.

dlftls38 4년 전 0

오!! 말씀하신대로 점화식을 세워보니 답이 거의 나왔습니다!! 감사합니다

제가 세운건 아예 답에 근접하지 못하는데 왜 이 점화식은 답이 나오는 건가요? 무슨 차이인지 모르겠습니다

n이 증가하는 형식으로 세워야해서그런건가요?? 합 구하기에서는 모두 똑같은 n이기에 저도 그렇게한거였는데..

그런데 이 점화식으로 행렬을 출력해보면 예제의 1~4는 제대로나오는데 5는 나오지 않습니다. a,b를 아직 사용하지 않아서 그런것 같은데

어디에 대입해야하나요?? 피보나치로 구한 값을 그림의 맨 오른쪽 행렬의 ZZ(0,N-1), ZZ(0,N)에 넣어야 할 것 같은데 답이 나오질 않습니다

지금 폰이라서 길게는 못 적는데 배열을 한 번 곱하면 인덱스가 1 커지게 해야 이 풀이가 의미가 생깁니다. 그래야 똑같은 행렬을 계속 곱해가며 다음 상태를 구할 수 있는거고 계속 똑같은 행렬이니까 행렬 거듭제곱을 할 수 있는 겁니다. 그러면 초기상태, 즉 n=0이든 1이든 맨 처음에 알고있는 상태가 있을 거 아니에요. 그러니까 이 문제면 ZZ(0, 0) ZZ(0, 1) ZZ(1, 1) ZZ(2, 1)...은 이미 값을 알잖아요. 여기에다가 저 행렬의 d-1제곱을 곱하면 ZZ(0, d-1) ZZ(0, d) ZZ(1, d) ZZ(2, d)...가 되는 거죠

dlftls38 4년 전 0

감사합니다!

이해한대로 대입해봤는데

마지막 예제가 잘안되네요. 초기값을 잘못 주고있는 것 같은데..

초기값을 ZZ(0, 0) ZZ(0, 1) ZZ(1, 1) ZZ(2, 1)라면

0 a a a a a...

그보다 n이 하나 크다면

a, b, a+b, 2a+b, 3a+b.... 될텐데 다 해봐도 잘 안되네요....ㅠ

sait2000 4년 전 1

0 0에 b-a를 주셔야한다니까요

dlftls38 4년 전 0

죄송합니다 ㅠㅠ 뭐가 문제인지 모르겠습니다

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <limits.h>
#include <functional>
#include <math.h>
#include <fstream>
#define INF 987654321

using namespace std;
const int MOD =  1000000009;

vector<vector<long long>> matrix_mul(vector<vector<long long>>& a, vector<vector<long long>>& b){
	int i,j,k;
	int n = a.size();
	vector<vector<long long>> c(n, vector<long long>(n));
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			for (k = 0; k < n; k++)
			{
				c[i][k] += a[i][j] * b[j][k];
				c[i][k] %= MOD;
			}
		}
	}
	return c;
}
int main(){
	int tc;
	scanf("%d",&tc);
	while(tc--){
		int i,j;
		long long a,b,c,d;
		scanf("%lld%lld%lld%lld", &a,&b,&c,&d);
		
		int SIZE = c+2;              
		vector<vector<long long>> ans(SIZE, vector<long long>(SIZE,0));
		vector<vector<long long>> arr(SIZE, vector<long long>(SIZE,0));
		
		for(i = 0; i < SIZE; i++){
			ans[i][i] = 1;	                // 단위 행렬 
		}
		for(i = 0; i < SIZE; i++){
			for(j=0;j<i+1;j++){
				arr[i][j]=1;                 // 점화식  
			}
		}
		arr[0][0]=0;
		arr[0][1]=1;                         //점화식
		
		d--;
		while (d > 0)
		{
			if (d % 2 == 1)
			{
				ans = matrix_mul(ans, arr);
			}
			arr = matrix_mul(arr, arr);
			d /= 2;
		}
		
		printf("\n"); 
		for(i = 0; i < SIZE; i++){
			for(j = 0; j < SIZE ; j++){
				printf("%d ",ans[i][j]);
			}
			printf("\n");
		}
		printf("\n");
		
		long long res=ans[SIZE-2][0]*(b-a);
		for(i=1;i<SIZE;i++){
			res+=ans[SIZE-1][i]*(a);
			res%=MOD;
		}
		printf("%lld\n",res);
		printf("\n-------------------\n");
	}
}

sait2000 4년 전 2

80번 줄에 SIZE-1같은데요. 그리고 저렇게 하면 a>b이면 나머지가 음수로 계산될 수 있어요

http://boj.kr/7abae411badf4db6...

그거 두 개 고쳐서 맞았습니다 받았네요

dlftls38 4년 전 0

나머지 부분은 염두하고있었는데 80번째 줄을 바보같이했었네요...

코앞까지 와놓고 생쇼하고있었네요 ㅠㅠ 정말 감사합니다!! 그림을 하도 그려서 비교하느라 SIZE-2로 헷갈렸었나봐요..

온몸에 전율이 흘렀습니다

많은 것을 배워갑니다 감사합니다

초기값을 줘야하는 경우 n-1번 행렬 곱셈후 초기값 행렬을 곱하는 부분, 이제 확실히 처리할 수 있겠네요 감사합니다.

다시생각해보면 고등학교때 해본것같은데 절대 안떠올랐네요

그런데 궁금한점이있습니다! 이 문제의 경우 점화식이 다양한 형식이 나올수 있을텐데

sait2000님께서는 파랑색 ㄴ 과같은 모양으로 점화식을 구하셨는데 그 이유가 초기값 a,b가 모두 포함하기 좋은 모양이라 그러신건가요??

저는 (0,0)에 b-a를 추가하면 d가 1일때 (0,-1)이 없이 어쩌지.. 했는데 테스트해보니 d가 1이면 단위행렬과 곱해져서 잘 처리가되더군요 ㅠㅠ 소름

그래서 제가 생각한건 저 빨강색으로 ㄴ을 뒤집은 모양인데, 정확히는 (0,1)은 건너뛰고 구하게되면 행렬이 구해지길래 대입해서 테스트해보면 답이 안나오더군요..

점화식을 구하는데에 고려할 점이 있는 것인가요?? 어떻게 세우시게된건가요??

sait2000 4년 전 0

빨강도 될 텐데요 그냥 무조건 한 번 곱하면 인덱스가 1칸 밀리게 행렬을 잘 만들면 돼요

dlftls38 4년 전 0

혹시 가능하시면 코드 조금만 봐주실수있나요 달라진점은 몇 개 없거든요

빨간색 방식의 점화식인데 SIZE는 그 전 점화식보다는 1 작고 초기값이 b-a가 아닌 b인 건데

혹시 초기값에 (0,2)가 들어가서 안되는 걸까요 (c,0)~(c,1)이 들어가야하는데 d가 2라서 안되는건지...

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <limits.h>
#include <functional>
#include <math.h>
#include <fstream>
#define INF 987654321

using namespace std;
const int MOD =  1000000009;

vector<vector<long long>> matrix_mul(vector<vector<long long>>& a, vector<vector<long long>>& b){
	int i,j,k;
	int n = a.size();
	vector<vector<long long>> c(n, vector<long long>(n));
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			for (k = 0; k < n; k++)
			{
				c[i][k] += a[i][j] * b[j][k];
				c[i][k] %= MOD;
			}
		}
	}
	return c;
}
int main(){
	int tc;
	scanf("%d",&tc);
	while(tc--){
		int i,j;
		long long a,b,c,d;
		scanf("%lld%lld%lld%lld", &a,&b,&c,&d);
		
		int SIZE = c+1; // 그 전 점화식은 c+2 
		vector<vector<long long>> ans(SIZE, vector<long long>(SIZE,0));
		vector<vector<long long>> arr(SIZE, vector<long long>(SIZE,0));
		
		for(i = 0; i < SIZE; i++){
			ans[i][i] = 1;	                // 단위 행렬 
		}
		for(i = 0; i < SIZE; i++){
			for(j=0;j<i+1;j++){
				arr[i][j]=1;                 // 점화식  
			}
		}

		d--;
		while (d > 0)
		{
			if (d % 2 == 1)
			{
				ans = matrix_mul(ans, arr);
			}
			arr = matrix_mul(arr, arr);
			d /= 2;
		}
		
		printf("\n"); 
		for(i = 0; i < SIZE; i++){
			for(j = 0; j < SIZE ; j++){
				printf("%d ",ans[i][j]);
			}
			printf("\n");
		}
		printf("\n");
		
		long long res=(ans[SIZE-1][0]*(b))%MOD; // b-a가 아닌 b 
		for(i=1;i<SIZE;i++){
			res+=ans[SIZE-1][i]*(a);
			res%=MOD;
		}
		printf("%lld\n",res);
		printf("\n-------------------\n");
	}
}
/*
5
1 1 1 1
1 1 1 4
1 1 2 3
1 1 5 5
24995 8633 1 25158567
*/

sait2000 4년 전 1

행렬이 틀렸네요 행렬을

110000..

100000..

101000...

101100...

101110...

이렇게 잡아야 할 걸요

dlftls38 4년 전 0

어떤 느낌인지 알겠습니다.

왼쪽 행렬과 오른쪽 행렬 점화식 형태가 똑같아야하군요 같은차이의 n만큼으로.

이것도 지금에서야 생각해보면 당연한것같은데 아무튼 그렇군요

바로 AC받았네요

정말 감사합니다 많은걸배웠습니다.

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

문제

문제

출처

ICPC

9341 ZZ 점화식 힌트 주실수있나요?

dlftls38 4년 전 1

sait2000 4년 전 1

dlftls38 4년 전 0

sait2000 4년 전 1

sait2000 4년 전 0

dlftls38 4년 전 0

sait2000 4년 전 1

dlftls38 4년 전 0

sait2000 4년 전 1

dlftls38 4년 전 0

sait2000 4년 전 1

dlftls38 4년 전 0

sait2000 4년 전 2

dlftls38 4년 전 0

sait2000 4년 전 0

dlftls38 4년 전 0

sait2000 4년 전 1

dlftls38 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말