[백준 11057 C++] 오르막 수

11057번: 오르막 수 (acmicpc.net)

11057번: 오르막 수

---

 

 

 

2차원 배열에 i길이의 j로 끝나는 오르막 수의 개수를 구해보자

	0	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1	1
2	1	2	3	4	5	6	7	8	9	10
3	1	3	6	10

- 0으로 끝나는 수는 길이가 몇이든 1이다 (0, 00, 000 ...)

- 길이가 1인 수는 모두 1개, 길이가 2인 수는 1개씩 증가

 

1로 끝나는 수는

길이가 1이면 1개 (1)

길이가 2이면 2개 (01, 11)

길이가 3이면 3개 (001, 011, 111)

 

2로 끝나는 수는

길이가 1이면 1개 (2)

길이가 2이면 3개 (02, 12, 22)

길이가 3이면 6개 (002, 012, 022, 112, 122, 222)

 

3으로 끝나는 수는

길이가 1이면 1개 (3)

길이가 2이면 4개 (03, 13, 23, 33)

길이가 3이면 10개 (003, 013, 023, 033, 113, 123, 133, 223, 233, 333)

 

-> arr[1][2] = arr[1][1] + arr[0][2]

arr[i][j] = arr[i][j-1] + arr[i-1][j]

 

---

이대로 코드를 짜고 예시 출력 결과가 맞아서 채점 돌려보니까 틀렸다..

문제의 코드는,,

#include <iostream>

using namespace std;

int main()
{
    int arr[1001][10];
    
    
    for(int i=0; i<10; i++){
        arr[0][i] = 1;
    }
    
    
    for(int i=0; i<1001; i++){
        arr[i][0] = 1;
    }
    
    for(int i=1; i<1001; i++){
        for(int j=1; j<10; j++){
            arr[i][j] = (arr[i][j-1] + arr[i-1][j]) % 10007;
        }
    }
    
    int n;
    cin >> n;
    
    int sum=0;
    for(int i=0; i<10; i++){
        sum += arr[n-1][i];
    }
    
    cout << sum << "\n";

    return 0;
}

백준 10844 쉬운 계단 수 c++ (tistory.com)

백준 10844 쉬운 계단 수 c++

.내가 놓친 한 줄의 코드가 있었다,,

바로 마지막 줄에 sum 또한 10007로 나눠줘야했던 것

난 애초에 배열에 넣을 때 10007로 나눠서 저장을 했기 때문에 괜찮다고 생각했는 데

생각해보니 sum으로 0~10까지 더해지는 데 숫자가 엄청 커지게 되면 10007을 넘는 수가 출력될 수 있겠구나

cout << sum %10007 << "\n";

 

이렇게 마지막 줄을 바꿔줬더니 맞았다!!

최종 코드는요

#include <iostream>

using namespace std;

int main()
{
    int arr[1001][10];
    
    
    for(int i=0; i<10; i++){
        arr[0][i] = 1;
    }
    
    
    for(int i=0; i<1001; i++){
        arr[i][0] = 1;
    }
    
    for(int i=1; i<1001; i++){
        for(int j=1; j<10; j++){
            arr[i][j] = (arr[i][j-1] + arr[i-1][j]) % 10007;
        }
    }
    
    int n;
    cin >> n;
    
    int sum=0;
    for(int i=0; i<10; i++){
        sum += arr[n-1][i];
    }
    
    cout << sum %10007 << "\n";

    return 0;
}