백준/ Gold 5 문제 , 백준 파이썬 2225 , 합분해

백준/ Gold 5 문제 , 백준 파이썬 2225 , 합분해

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
dfs 로 접근하려다가 시간만 잡아먹고 풀이를 바꿨다. 직접 경우의 수들을 나열해보고 규칙을 찾아본다음 그 이후 값도 예상해서 풀어보니 통과!

 

<문제 출처>

 

https://www.acmicpc.net/problem/2225

2225번: 합분해

 

------------------------------------------------------------------------------------------------------------------------------

 

 

 

 

공책에 N=5, K=5 까지 한번 나열해봤다.

 

주의할 점은 0도 연산에 들어간다는 점이다.

 

 

1열 K=1 일때는, N에 상관없이 무조건 1가지만 존재한다. N 값 그대로의 경우밖에 없기 때문.

 

 

2열 K=2 일때부터 값이 변하기 시작하는데,

 

1은 0+1, 1+0   2가지

 

2는 1+1, 2+0, 0+2   3가지

 

3은 1+2, 2+1, 3+0, 0+3  4가지

 

4는 1+3, 3+1, 2+2, 0+4, 4+0  5가지

 

점점 한가지씩 증가한다.

 

------------------------------------------------------------------------------------------------------------------------------

 

1행 N=1 일때도 봐보자.

 

K=1     1   1가지

 

K=2     1+0 , 0+1    2가지

 

K=3     1+0+0, 0+1+0, 0+0+1   3가지

 

K=4     1+0+0+0, 0+1+0+0, 0+0+1+0, 0+0+0+1   4가지

 

K의 값에 맞게 증가한다.

 

참고로 이 값은 자릿수 크기에 1을 배치하는 값이랑 동일하므로 조합 nC1 의 값이랑 동일하다.

 

 

 

2행 N=2 일때

 

K=1   2   1가지

 

K=2    1+1, 2+0, 0+2    3가지

 

K=3    1+1+0 을 배치하면 3가지,  2+0+0 을 배치하면 3가지  총 6가지

         3C2                                   3C1

 

K=4   1+1+0+0  을 배치하면 6가지,   2+0+0+0 을 배치하면 4가지   총 10가지

         4C2                                         4C1

 

K=5   1+1+0+0+0 을 배치하면 10가지,   2+0+0+0+0 을 배치하면 5가지   총 15가지

         5C2                                         5C1

 

 

일반화 해보면 nC2 + nC1 (n=K) 의 값이 N=2 일때의 값들이다.

 

 

 

 

여기까지 행렬의 2행과 2열까지의 값들을 구한 상태이다. 정확한 규칙이 바로 보이지는 않지만

 

3행 3열의 값이 10이 나오게 된다면 어느정도 이후의 값을 유추해 볼 수가 있다.

 

N=3, K=3 일때,

 

3+0+0    배치하면 3가지     3C1

 

2+1+0    배치하면  6가지     3P2

 

1+1+1    1가지

 

총 10가지의 값이 나온다.

 

 

 

여기까지 구해보고 추측해볼 수 있는 값은

 

i행 j열의 값은 i-1행 j열의 값과 i행의 j-1열의 값을 더했을때의 값이 나오겠다 라는것을 짐작할 수 있다.

 

 

이를 통해 4행 3열의값은 15  , 3행 4열의 값은 20 이라고 추측할 수 있고 직접 다 구해본결과 동일한 값이 나왔다.

 

 

 

이것을 이제 코드로 나타내보면,

 

 

이렇게 한행씩 열을 쭉 만들어나아가서 인덱스를 맞춰주기 위한 0행 0열을 제외한

200행 200열의 행렬을 만들어낼 수 있다. 

 

 

이후 N과 M의 값을 입력받아 알맞은 위치에 있는 값만 출력시켜주면된다.

 

 

 

 

 

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

정답

 

 

 

 

 

 

matrix=[[1]*201 for _ in range(201)]

for i in range(1,201):
    matrix[1][i]=i

for i in range(2,201):
    for j in range(2,201):
        matrix[i][j]=matrix[i-1][j]+matrix[i][j-1]

N,M=map(int,input().split())
print(matrix[N][M]%1000000000)