Two Pointer
-
Q. 5642. 합(D3)코딩테스트/SWEA_Java 2023. 5. 17. 12:22
Q. 5642. 합(D3) 0. 문제 D3 난이도의 문제이고, DP를 이용한 문제이다. 수열이 주어지고 연속해서 원소를 골라 합을 구할 때, 그 합의 최대가 몇인지 구하는 프로그램을 작성하는 문제이다 1. 풀이 두 가지의 풀이 방법이 생각났다. 첫번재는 DP를 이용한 풀이이고, 두 번째는 투 포인터를 이용한 풀이이다. 1-1 DP를 이용한 풀이 DP인 경우 보통 정답이 dp[N - 1]인데, 이 문제의 경우는 그렇게는 정답을 구할 수 없어서 조금 시간이 걸렸다. 아래와 같은 방식으로 풀었다. 1) 반복문을 N-1까지 돌면서, 현재 인덱스의 숫자와 이전에 저장된dp + 현재 인덱스의 숫자를 비교해 큰 값을 dp에 저장한다. 2) dp 배열에 저장된 값 중 최대값을 저장한다. 코드는 아래와 같다. impor..