seyhu2000   4년 전

안녕하세요.


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


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


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

yys11631   4년 전

31번 째 줄에 =이 아니라 +=이 아닐까요

seyhu2000   4년 전

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

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

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


저같은 경우에는

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

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

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

yys11631   4년 전

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

seyhu2000   4년 전

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


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   4년 전

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

seyhu2000   4년 전

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

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

해당 문제 해결했어요.

기분이 너무 좋네요^^

seyhu2000   4년 전

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

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

yys11631   4년 전

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

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