[BOJ]#2225 합분해 Python
문제
https://www.acmicpc.net/problem/2225
0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.
덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.
입력
첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.
출력
첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.
아이디어
k=1인 경우,
경우의 수는 n의 값과 상관없이 모두 1
k=2인 경우,
경우의 수는 n+1
ex)n=4이면,
(0, 4)(1, 3)(2, 2)(3, 1)(4, 0) => 5개
k>=3인 경우,
우선 k=2이 경우와 같이 두 개로 자른 후 k값에 따라 다시 자른다.
ex)n=4, k=3이면,
(0, 4)(1, 3)(2, 2)(3, 1)(4, 0)에서 뒤의 숫자만 다시 두 개로 자른다.
(0, 4) => 4를 두 개로 자른다 => data(4,2)=5
(1, 3) => 3을 두 개로 자른다 => data(3,2)=4
(2, 2) => 2를 두 개로 자른다 => data(2,2)=3
(3, 1) => 1을 두 개로 자른다 => data(1,2)=2
(4, 0) => 0을 두 개로 자른다 => data(0,2)=1
==>data(4,2)+data(3,2)+data(2,2)+data(1,2)+data(0,2)
==>5+4+3+2+1=15개
표로 표현하면 다음과 같다
k, n 0 1 2 3 4 5 1 1 1 1 1 1 1 2 1 2 3 4 5 6 3 1 3 6 10 15 21
data(n,k)=data(n,k-1)+data(n-1,k-1)+data(n-2,k-1)+...+data(0,k-1)
data(n-1,k)=data(n-1,k-1)+data(n-2,k-1)+data(n-3,k-1)+...+data(0,k-1)
==>data(n,k)=data(n,k-1)+data(n-1,k)
내 코드(Python) Error
첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.
첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.
아이디어
k=1인 경우,
경우의 수는 n의 값과 상관없이 모두 1
k=2인 경우,
경우의 수는 n+1
ex)n=4이면,
(0, 4)(1, 3)(2, 2)(3, 1)(4, 0) => 5개
k>=3인 경우,
우선 k=2이 경우와 같이 두 개로 자른 후 k값에 따라 다시 자른다.
ex)n=4, k=3이면,
(0, 4)(1, 3)(2, 2)(3, 1)(4, 0)에서 뒤의 숫자만 다시 두 개로 자른다.
(0, 4) => 4를 두 개로 자른다 => data(4,2)=5
(1, 3) => 3을 두 개로 자른다 => data(3,2)=4
(2, 2) => 2를 두 개로 자른다 => data(2,2)=3
(3, 1) => 1을 두 개로 자른다 => data(1,2)=2
(4, 0) => 0을 두 개로 자른다 => data(0,2)=1
==>data(4,2)+data(3,2)+data(2,2)+data(1,2)+data(0,2)
==>5+4+3+2+1=15개
표로 표현하면 다음과 같다
k, n 0 1 2 3 4 5 1 1 1 1 1 1 1 2 1 2 3 4 5 6 3 1 3 6 10 15 21
data(n,k)=data(n,k-1)+data(n-1,k-1)+data(n-2,k-1)+...+data(0,k-1)
data(n-1,k)=data(n-1,k-1)+data(n-2,k-1)+data(n-3,k-1)+...+data(0,k-1)
==>data(n,k)=data(n,k-1)+data(n-1,k)
내 코드(Python) Error
k=1인 경우,
경우의 수는 n의 값과 상관없이 모두 1
k=2인 경우,
경우의 수는 n+1ex)n=4이면,
(0, 4)(1, 3)(2, 2)(3, 1)(4, 0) => 5개
k>=3인 경우,
우선 k=2이 경우와 같이 두 개로 자른 후 k값에 따라 다시 자른다.ex)n=4, k=3이면,
(0, 4)(1, 3)(2, 2)(3, 1)(4, 0)에서 뒤의 숫자만 다시 두 개로 자른다.
(0, 4) => 4를 두 개로 자른다 => data(4,2)=5
(1, 3) => 3을 두 개로 자른다 => data(3,2)=4
(2, 2) => 2를 두 개로 자른다 => data(2,2)=3
(3, 1) => 1을 두 개로 자른다 => data(1,2)=2
(4, 0) => 0을 두 개로 자른다 => data(0,2)=1
==>data(4,2)+data(3,2)+data(2,2)+data(1,2)+data(0,2)
==>5+4+3+2+1=15개
표로 표현하면 다음과 같다
k, n 0 1 2 3 4 5 1 1 1 1 1 1 1 2 1 2 3 4 5 6 3 1 3 6 10 15 21 data(n,k)=data(n,k-1)+data(n-1,k-1)+data(n-2,k-1)+...+data(0,k-1)
data(n-1,k)=data(n-1,k-1)+data(n-2,k-1)+data(n-3,k-1)+...+data(0,k-1)
==>data(n,k)=data(n,k-1)+data(n-1,k)
((n+1)(n+2))/2가 계속 반복되는데 하나씩 조건을 추가하다가 이상해짐
import sys input = lambda: sys.stdin.readline() def findNum(num, k): cnt = 0 if k == 2: cnt += num+1 elif k == 3: cnt += ((num+1)*(num+2))/2 else: for j in range(0,num+1): cnt += ((j+1)*(j+2))/2 k -= 1 if k != 3: cnt += findNum(num, k) return cnt n, k = map(int, input().split()) cnt = 0 if k == 1: cnt = 1 else: cnt = findNum(n, k) print(int(cnt))
다른 코드(Python)
import sys
input = lambda: sys.stdin.readline()
n, k = map(int, input().split())
data=[1]
data += [0]*n
for i in range(1,k+1):
for j in range(1, n+1):
data[j]=(data[j]+data[j-1])%1000000000
print(data[n])
Author And Source
이 문제에 관하여([BOJ]#2225 합분해 Python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@guswl8280/BOJ2225-합분해-Python
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import sys
input = lambda: sys.stdin.readline()
n, k = map(int, input().split())
data=[1]
data += [0]*n
for i in range(1,k+1):
for j in range(1, n+1):
data[j]=(data[j]+data[j-1])%1000000000
print(data[n])
Author And Source
이 문제에 관하여([BOJ]#2225 합분해 Python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@guswl8280/BOJ2225-합분해-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)