고려사항
이번 문제 로직은 어렵지 않았으나 가장 최적의 벡터 메모리 할당을 고민하기 위해 많은 생각을 하였다.
2차원 벡터를 필요한 만큼만 초기화하고 싶어서 많은 고생을 했다.
일단 필요한 공간은 아래와 같다.
dp[0] -> 1 : 1 dp[1] -> 2 : 2 1 dp[2] -> 3 : 3 3 1 dp[3] -> 4 : 4 6 4 1 dp[4] -> 5 : 5 10 10 5 1 dp[5] -> 6 : 6 15 20 15 6 1
정확이 대칭을 만들기 위해 첫 칸을 1로 채워준 후
dp[0] -> 1 : 1 1 dp[1] -> 2 : 1 2 1 dp[2] -> 3 : 1 3 3 1 dp[3] -> 4 : 1 4 6 4 1 dp[4] -> 5 : 1 5 10 10 5 1 dp[5] -> 6 : 1 6 15 20 15 6 1
중복되는 값을 없애기 위해 절반으로 나누면