Dazzling 개발 노트

[백준] 1912 - 연속합 (Java) 문제 https://www.acmicpc.net/problem/1912 풀이/후기 DP 문제를 계속해서 풀면서 정말 오랜만에 자력으로 점화식을 도출해냈다. 아주 자신감있게 풀어서 주어진 예제가 모두 맞게 나오는 것을 확인하고 제출하니 오답이 나왔다. dp[i] = Math.max(dp[i-1], arr[i-1]) + arr[i]; 이 점화식에선 무조건 두 개 이상의 숫자를 선택한 경우이다. 연속된 몇 개의 수를 선택하는 경우 외에 하나의 수만 선택할 수도 있으므로 arr[i]는 꼭 더해져야 하는 부분이 아니다. dp[i] = Math.max(dp[i-1] + arr[i], arr[i]); 이렇게 수정하니 정답처리가 되었다. 정말 오랜만에 자신있게 풀었는데,, 마무..

[백준] 11053 - 가장 긴 증가하는 부분 수열 (Java) 문제 https://www.acmicpc.net/problem/11053 풀이/후기 처음에는 문제를 잘못읽고 풀어서 오답이 나왔다. 그리고 dp에 수열 중 선택한 값을 저장하는 방식으로 풀었는데 생각해보니까 수열의 크기를 구해야하기 때문에 dp에 부분 수열의 번호를 넣어서 풀어야 했다. 마지막에 dp[N-1]을 출력하면 당연히 답이 나와야한다고 생각했는데 N-1번째 숫자가 부분 수열의 멤버가 아닐 수 있기 때문에 그렇게 하면 안된다. 반복문을 한 번 더 돌려서 dp의 가장 큰 값을 뽑아서 출력한다. 코드 package DynamicProgramming; import java.io.*; import java.util.*; public clas..