[수업]정수 합

Intro..

이 문제는 DP로 풀기 가능한 문제이다.

DP 관련해서 정리해둔 게시글이 있기 때문에 참고할 것.

문제

풀이

내가 푼 방식은 너무 좀 규칙들이 엉망이라고 생각한다.
교수님 풀이 방식이 훨씬 코드가 짧다. 이점을 참고할 것.

우선, 표처럼 초기값을 1번, 2번라인 다 채우고, (i,i)라인도 싹다 채울 수 있다.

그 후 2*k가 n 이상이면 초과만큼 ‘1’이 있는거라서 ‘1’ 없이 생각할수 있으니까 (n-초과,k-초과) 부분 값을 사용(표에 대각선 동일값 반복 그부분임)

• 이상 이니까 만약 값 같을땐 dp배열(i-1,j-1)인 이전값에 +1만 추가!(표에 bold체 그부분임)

• 즉, 13 7예로(n k)
  1 1 1 1 1 1 7
  1 1 1 1 1 2 6
  1 1 1 1 1 3 5
  1 1 1 1 1 4 4
  1 1 1 1 2 2 5
  1 1 1 1 2 3 4
  1 1 1 1 3 3 3
  1 1 1 2 2 2 4
  1 1 1 2 2 3 3
  1 1 2 2 2 2 3
  1 2 2 2 2 2 2
  로 손으로 풀 수 있는데 특징이 맨앞 1을 제외해보면??

• 12 6(n k)의 값이다.
• 그리고 2 2 2…가 최대 k(=7)만큼 들어갈 수 있으니 2*7을 하면 14로 1 초과이다.
• 초과는 반드시 이 형태라서 앞의 1이 전부 동일하니까 앞의 1을 없이 볼 수 있다는 말이다.
• 그럼 이 경우 dp(i-1,j-1)의 값이다.
  • (만약 14 7이면?? 2*7=14니까 2 2 2 2 2 2 2로 끝나겠죠.
    따라서 2*k가 n과 같을땐 dp(i-1,j-1)에 +1로 한개 추가하란것.)

만약 크기가 미만때는 dp(i-1, j-1)에 추가 값들을 적용

• 위에서 예시를 보여준것을 보면 맨앞이 ‘1’로만 구성되어있는데,
• 이 경우에는 맨앞이 ‘2’, ‘3’… 등등도 있는 경우이다.
• 이부분은 따로 처리해서 추가 값이라고 생각하고 dp(i-1,j-1)값에 더해준다.
  • dp(i-1, j-1)은 맨앞이 ‘1’로 구성된 부분 값으로 보자. 추가 값들은 맨앞이 ‘1’이 아닌것들로 보자.

• 추가값은 어떻게 구하나?? 아래 코드 참고.

  for (k = 2; k <= j; k++) { // 2,3,4... n까지 곱해보고 계속 작은 수들만 고려  
  	if (k * i <= j) {  
  		oneNum = j - (k * i); // 2*k와 n의 차이값  
  		oneNum += i - 1; // i-1 더함  
  		dpArr[i][j] = (dpArr[i][j] + dpArr[i - 1][oneNum]) % MOD;  
  	}  
  }
  

  • 즉, 2*k했을때 n보다 미만인건 당연히 13 7(n k) 의 예시로보면 1 2 2 2 2 2 2 가 못온다는 거니까 dp(i-1, j-1)을 온전히 사용불가.
  • 따라서 위 코드 방법으로 구해주면 됨(코드에 j는 n으로 보면 된다.)
    참고로 dpArr[k][n] 형태임.

• 12 3(n k)의 예로 보면,
  1 1 10
  1 2 9
  1 3 8
  1 4 7
  1 5 6 => 여기까지가 dp(i-1,j-1)값. 이후부턴 추가값
  2 2 8
  2 3 7
  2 4 6
  2 5 5
  3 3 6
  3 4 5
  4 4 4
  여기서 추가값인 2, 3, 4(맨앞 숫자)의 경우를 구해줘서 dp(i-1,j-1)값에 더해줘야 하는것이다.

  • (i-1,j-1)은 11 2(n k)이다. 그리고 2,3,4인지 구하는거는 2*3=6, 3*3=9, 4*3=12로 초과가 아닌지 확인하면 된다 => 초과가 아님
  • 이제 2, 3, 4의 경우를 다 구하면됨. 각자 n과 차이값은 12-6, 12-9, 12-12 이고 6, 3, 0이다.
  • 이값에 k값인 11 2(n k)에서 2를 각각에 더해준다.
  • 그럼 8 2, 5 2, 2 2(n k) 가 나오며 이들을 더하면 추가값이 구해진다.
    • 분명 풀때는 이렇게 했는데, 지금보니 차이값에 k값을 왜더해줬던건지 기억이.. 안난다ㅜㅜ

교수님 풀이!! => 훨씬 간단하게 푸신것 같다

• 코드에서 calc(n, n0, k) 함수가 핵심
  • n을 k개의 정수를 더해서 나타내는 방법의 수(n0는 시작 정수)

시작 정수 n0는 1로 맨처음 시작하였다. 즉, calc(n, 1, k); //이것이 최종 구할 값

k는1일때 if(n>=n0) 부분은?

• 정수는 한개(k=1)이고, 그 정수인 n0가 n보다 작거나 같으면 경우 1개 성립한다.
• 당연히 else라면, 경우 1개로 성립불가하다.

다음 for문에서 sum값 구하는 부분은?

• 재귀로 접근하며, 시작정수가 1이라면 n까지 다 접근해서 모든 경우를 구하는 느낌이다(for문 동작 흐름)

• r = calc(n-i, i, k-1); 을 보면 n0를 i로 n을 n-i로 k를 k-1로 주면서 재귀를 하는데 이를 위해선 당연히 n-i < i 가 되면 안되기 때문에 먼저 조건문으로 확인하는 것이다.