SGU 135 Drawing Lines(dp)

Description은 종이 한 장을 n번 자르면 최대 몇 부분으로 나뉘는데 Input은 하나의 정수 n(0<=n<=65535) Output 출력은 종이 한 장을 n번 자르면 최대 몇 부분으로 나뉘어집니다. Sample Input 0 Sample Output 1 Solution은 간단한 dp입니다. dp[i]를 설정하면 종이 한 장에 i번 자르면 최대 몇 부분으로 나뉘어집니다. 그러면 i+1번에서 많게는 전 i번까지 교차합니다. 즉, dp[i]를 바탕으로 i+1 부분을 자르고그러므로 전이 방정식 dp[i]=dp[i-1]+i가 있는데 그 중에서 dp[0]=1이므로 dp[i]=i*(i+1)/2+1 코드가 있다.

#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    printf("%lld
",1ll*n*(n+1)/2+1);
    return 0;
}