Little Jay

Prefix Sum문제. 문제에서 정확히 뭘 출력하라고 하는지만 파악하면 쉽게 풀 수 있다. #include #define endl '\n' using namespace std; int dp[1025][1025]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; int x1, y1, x2, y2; cin >> n >> m; for (int i = 1; i dp[i][j]; for (int i = 1; i y1 >> x2 >> y2; cout

DP가 하도 어려워서 요새 DP를 집중적으로 공부하고 있다. 그 와중에 조금 어이없는(?) 문제를 발견해서 풀이를 올리고자 한다. 위 문제는 어떤 실수 형태의 배열에서 연속되는 구간의 곱의 최대값을 출력하는 문제이다. 이를 간단하게 구성을 construct해보면 어떤 배열이 자기 자신으로 초기화 된 후에, 그 0번 인덱스의 것을 제외하고 1번 인덱스부터 자기 자신과 그 전에 있는 것의 곱의 대소 비교를 통해서 누적곱을 구할 수 있다. 이렇게 업데이트 시켜 주면서 최대값을 찾아주면 정답인데, C++를 하는 사람들은 당연히 setprecision 메서드를 사용했을 것이다. 문제는 이렇게 하면 정답이 아니다. 문제에서 요구한 것은 어떤 값들이 들어와도 소수 3번째 자리수까지 출력하는 것이다. 정수값을 setp..

문제를 잘 곱씹어보면 아이디어가 하나 떠올랐는데, 백준 문제의 '가장 긴 증가하는 부분 수열' 이 떠올랐다. 생각해보면 이 아이디어가 Correct하게 맞아떨어지는데, 이는 해당 구간에서 오름차순으로 증가하는 수열이 결국 이 문제의 상자와 같기 때문이다. #include #define endl '\n' using namespace std; int n; int dp[1001]; int arr[1001]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1; i > arr[i]; } int ans = -1; for (int i = 1; i