문제 설명
다음의 점화식에 의해 정의된 수열 t(n)을 생각하자:
t(0)=1
t(n)=t(0)t(n-1)+t(1)t(n-2)+...+t(n-1)*t(0)
이 정의에 따르면,
t(1)=t(0)t(0)=1
t(2)=t(0)t(1)+t(1)t(0)=2
t(3)=t(0)t(2)+t(1)t(1)+t(2)t(0)=5
...
주어진 입력 0 ≤ n ≤ 35에 대하여 t(n)을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 n (0 ≤ n ≤ 35)이 주어진다.
출력
첫째 줄에 t(n)을 출력한다.
문제 분석 과정
주어진 점화식을 갖고 다이나믹 프로그래밍 알고리즘을 이용해 문제를 해결해야한다. 주어진 점화식은 다음과 같다.
점화식
동적 계획법이란 중복되는 데이터를 저장하고 재사용하는데의 의의 가있다.
문제에서 주어진 방식 (bottom-up) 방식으로 접근해 보자
t(3)을 알기 위해서는 t(2)를 알아야하고 t(2)을 알기 위해서는 t(1)를 알아야한다. 그러면 t(1)을 구한뒤 t(2)를구하고 그 다음 t(3)를 구해야한다.
점화식 분석이 끝났다. 그 다음 입력되는 값과 출력되는 값을 바라보자.
입력의 제한은 0 ≤ n ≤ 35 이다. 입력 데이터가 메모리에 영향을 줄 만큼 크지 않기 때문에 길이가 36 인 배열을 하나 생성하고 이 배열의 이름을 dp라고 하자. dp는 값을 기록하기 위한 배열이다.
이제 입력에 대한 분석도 끝났다.우리가 출력하고자하는 값은 dp[n] 이다.
아래코드는 이전 항들을 활용해서 현재 항을 찾는 방법을 이용한 코드이다.
소스코드
n = int(input())
dp = [0 for _ in range(36)]
dp[0] = 1
dp[1] = 1
dp[2] = 2
for i in range(3, n+1):
for j in range(i):
dp[i] += dp[j]*dp[i-1-j]
print(dp[n])오류나 질문에 대한 문의 댓글로 남겨주겨주세요!
