Stargazer

문제: 접근: 그냥 하나씩 접근해서 비교하여 푸는 방식으로 하면, 시간내로 풀지 못한다. 따라서 점화식을 이용해서 풀면 된다. 즉, DP로 풀면 시간내로 풀린다. 전략: 시간을 최소로 사용해야하기 때문에 데이터를 메모라이징하여서 저장한다. 점화식은 구간 [i,j] 가 있을때, i==j(구간길이 1)이면 true, 구간길이가 2일때, 입력데이터 input[i] == input[j] 가 같으면 true 아니면 false로 저장하고, 나머지 구간은 dp[i,j] = dp[i+1, j-1] && input[i] == input[j] 이면 된다. (이전 데이터를 이용해서, 양옆 한번만 비교하면 된다.) 코드: #include #include using namespace std; int n,m; vector su;..