글 읽기 - 고수님 부탁드려요

seyhu2000 7년 전 0

안녕하세요.

n을 어떤 값을 입력하더라도 10이 계속나옵니다.

어떤 점이 잘못됬는지 도저히 모르겠습니다.

고수님 설명 좀 부탁드려요~

#include<queue>
#include<vector> 
#include<iostream>
#include<stdio.h>
#include<algorithm>

using namespace std;

//#11057 포인트 : 0으로 시작가능, 같은수도 오름차순으로 간주

int main()
{

	int d[1001][11]; //행 : 숫자 길이 수, 열 : 첫째 자리 숫자, 배열의 값 : 오르막 수의 개수 ex) d[2][3] ==> 2 3X
	int n;
	int sum=0;
	scanf("%d", &n);

	for(int j=0;j<=9;j++) // 한단위수 처리 (기저조건)
	{
		d[1][j]=1;
	}


	for(int i=2;i<=n;i++) 
	{
		for(int j=0;j<=9;j++)
		{
			for(int k=j;k<=9;k++) //k는 j부터 9까지
			{
				d[i][j]= d[i-1][k] % 10007; 
			}

		}
	}

	for(int j=0;j<10;j++)
	{
		sum=(sum+d[n][j]) % 10007;

	}

	printf("%d\n", sum % 10007);
	return 0;
}

seyhu2000 7년 전 0

고맙습니다. +=는 이해를 했는데

k의 범위가 이해가 되지 않아서 질문드려요~~

j<=k<=9까지 되는게 아닌지해서요~

저같은 경우에는

d[i][j] (i: 숫자 길이 수, j : 첫째 자리 숫자, 배열의 값 : 오르막 수의 개수)

ex) d[2][3] ==> 2 3X

했는데 만일 j가 3이 왔을 경우 오르막 수가 되려면 3에서부터 9까지 되어야 하는게 아닌가해서요..

#include<queue>
#include<vector> 
#include<iostream>
#include<stdio.h>
#include<algorithm>
#define mod 10007

using namespace std;

int main()
{

	long long d[1001][11]; //행 : 숫자 길이 수, 열 : 첫째 자리 숫자, 배열의 값 : 오르막 수의 개수 ex) d[2][3] ==> 2 3X
	int n;
	long long sum=0;
	scanf("%d", &n);

	for(int j=0;j<=9;j++) // 한단위수 처리 (기저조건)
	{
		d[1][j]=1;
	}


	for(int i=2;i<=n;i++) 
	{
		for(int j=0;j<=9;j++)
		{
			for(int k=j;k<=9;k++) //k는 j부터 9까지
			{
				d[i][j]+=d[i-1][k] % mod; // 범위라서 더해줘야 함.
			}

		}
	}

	for(int j=0;j<=9;j++)
	{
		sum+=d[n][j] % mod; // n=1일때의 조건을 만족시키기 위해서 % mod를 함.

	}

	printf("%d\n", sum);
	return 0;
}

yys11631 7년 전 1

sum+=x%y를 실행한다면 sum=(sum+x)%y가 아니라 sum=sum+(x%y)를 실행합니다. 저렇게 실행한다면 sum이 int형을 초과할 때는 둘째 치고 10007이상일 때 %mod가 적용되지 않습니다. 생각한 알고리즘 자체는 맞았다고 생각합니다.

seyhu2000 7년 전 0

그러면 아래와 같이 변경해야 한다는 말씀이시죠?

d[i][j]+=d[i-1][k] % mod -> d[i][j]=(d[i][j]+d[i-1][k]) % mod

sum+=d[n][j] % mod -> sum=(sum+d[n][j]) % mod

그러나 역시 답이 안나오네요.

yys11631 7년 전 1

배열을 자동으로 0으로 초기화하려면 전역으로 선언하세요. 지역변수로 선언하면 하면 보통은 실행이 안되거나 쓰레기값이 들어있을겁니다. 또 세세한거지만 sum을 long long으로 선언했다면 출력도 %lld로 통일하세요.

seyhu2000 7년 전 0

역시 고수는 대단하십니다.

제가 잘 모르는 부분을 알려주셔서.

해당 문제 해결했어요.

기분이 너무 좋네요^^

seyhu2000 7년 전 0

고수님 제가 요새 dp문제를 주로 풀고 있는데 점화식 만들때 어떨땐 1차원배열쓰고 어떨땐 2차원배열을 쓰는데 어떻게하면 배열의 수를 알수 있을까요?

전 보통 점화식을 만들때 직전단계의 반복요소들의 관계로 접근을 합니다.

고수는 아니지만 답해보자면 다음 단계에 영향을 줄 수 있는 변수의 개수를 파악하는겁니다. 당연한 이야기지만 문제를 읽으면서 영향을 주는 것과 주지 않는 것을 구분하는 것을 빠르게 구분해야합니다. 보통 1차원 배열 dp는 낼 수 있는 문제 수준에 한계가 있고 3차원은 숫자가 조금만 커져도 시간 초과가 발생하니 조건이 단순한건 1차원, 나머지는 대부분 2차원 배열에 초점을 두고 생각해보세요. 이는 결국 많이 풀면서 패턴을 파악하는게 도움이 될텐데 https://code.plus/course/15에서 문제만 풀어보세요. 아마 엥간한건 검색 정도로 풀 수 있을겁니다.

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

문제

문제

출처

ICPC

고수님 부탁드려요

seyhu2000 7년 전 0

yys11631 7년 전 1

seyhu2000 7년 전 0

yys11631 7년 전 1

seyhu2000 7년 전 0

yys11631 7년 전 1

seyhu2000 7년 전 0

seyhu2000 7년 전 0

yys11631 7년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말