코드업(codeup) 3801 : 오르막 수 C언어

▶문제 : 오르막 수 (codeup.kr)

오르막 수

 

▶코드 작성

#include <stdio.h>

int arr[1001][10]; //자리수, 맨 앞자리 숫자 => 메모이제이션

void func(int d, int num) //최소숫자, 자리수
{
    for (int i = d; i <= 9 && num > 1; i++)//최소숫자 ~ 9 반복
    {
        if (arr[num - 1][i] == 0) func(i, num - 1);
        //현재 자리수에서 -1한 값이 없으면 재귀를 통해 알아내기
        arr[num][d] += (arr[num - 1][i]) % 10007;
        //현재 자리수 num에서 오르막이 되는 다음 자리수 num-1의 i자리값을 더함
    }
}

int main()
{
    int n;
    int cnt = 0;
    scanf("%d", &n);

    for (int i = 0; i <= 9; i++) arr[1][i] = 1;

    for (int i = 0; i <= 9; i++)
    {//실질적으로 i=0만 재귀가 이루어지고 나머지 1 ~ 9는 메모리제이션으로 값을 바로 얻을 수 있음
        func(i, n);
        cnt += arr[n][i];
        cnt %= 10007;
    }

    printf("%d", cnt);
    return 0;
}

 

▶해석

예를 들어 n=3이라면

먼저 첫째 자리는 개수가 1이므로 1로 맞췄다.

 

main함수의 for문이 i=0부터 시작한다.

1. func(0, n) 함수를 실행하면 func함수에서 반복문이 i=0부터 시작돼 둘째 자리 값의 유무를 확인한다.

2. 둘째 자리가 0일 때의 값이 없으니 재귀함수로 func(0, n-1) 함수를 실행한다.

3. 첫째 자리 값은 존재하므로 0부터 9까지의 값을 둘째 자리가 0일 때의 값에 모두 더해준다.

4. 모두 더하면 함수가 종료되어 다시 돌아와 셋째 자리가 0일 때의 값에 더해준다.

5. 마찬가지로 둘째 자리가 1일 때의 값이 없으면 func(1, n-1) 재귀를 통해 알아낸 후 셋째 자리가 0일 때의 값에 더해준다.

6. 모든 반복을 마치면 셋째 자리가 0일 때 둘째 자리가 0 ~ 9 일 때의 값이 모두 더해져 있을 것이다.

 

다시 main함수로 돌아와 i=0가 종료됐으므로 i=1가 시작된다.

i=1부터는 i=0때 둘째 자리 값을 모두 구했으므로 배열에 저장된 값을 그대로 더하면 된다.

(i=1는 둘째 자리가 1 ~ 9 일 때의 값을 모두 더한다.)

 

마지막으로 셋째 자리가 0 ~ 9 일 때의 값을 cnt에 더하면 된다.