구간의 시작과 끝중 하나를 선택할 수 있는 다이나믹 프로그래밍

1823번: 수확  왼쪽부터 오른쪽으로 n개의 벼가 있는데, 매번 맨 왼쪽 혹은 맨 오른쪽 중 하나를 수확할 수 있다 k번째 수확할때 그 벼의 가치가 A[i]라면, A[i] * k의 이익을 얻는다 n개의 벼를 모두 수확할 때 얻는 최대 이익은? --------------------------------------------------------------------------------------------------------------------------------------------------- dp[i][j]를 [i,j] 구간에서 벼를 수확할 때 얻는 최대 이익이라고 정의 i번째 벼를 수확하거나, j번째 벼를 수확할 수 있다 [i,j] 구간에 벼가 있다면 0 ~ i-1의 벼랑 j+1 ~ n-1..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 2. 26.
• textsms

n개의 구간 각각에서 어떤 정수들을 골라 합해 0을 만들 수 있는가?

https://atcoder.jp/contests/abc362/tasks/abc362_c C - Sum = 0AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  n개의 구간 (Li,Ri)가 주어질때, 이 구간들 각각에서 정수 Xi를 하나 골라 n개 합쳐서 0을 만들 수 있는지? 그렇다면 그러한 정수 배열을 하나 찾는 문제 먼저 그러한 정수 배열이 존재하는지 알 수 있을까? 이것부터 어렵더라고 근데 생각보다 간단했다  $$L_{1}$$ L_{2}  ...  $$L_{n}  이들을 합해도 부등식이 유지되므로,$$ \sum_{i =..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 8. 24.
• textsms

구간에 원소를 더하는 쿼리가 많이 주어질 때 필요한 누적합 테크닉(imos법)

19951번: 태상이의 훈련소 생활 (acmicpc.net) 19951번: 태상이의 훈련소 생활 2020년 5월 14일 논산훈련소에 입대한 태상이는 첫 총기 훈련에서 가스 조절기를 잃어버리는 중대한 실수를 범했다. 그로 인해, 태상이는 조교들에게 눈총을 받게 되었다. 조교들은 태상이에게 연 www.acmicpc.net 배열이 주어질때, 구간 [a,b]에 c를 더하는 쿼리가 여러개 주어지고, 모든 쿼리를 해결하고 나서 최종 배열을 구하는 문제 1 2 3 4 5 -1 -2 -3 -4 -5 라는 배열에서 [1,5]에 -3을 더하면... -2 -1 0 1 2 -1 -2 -3 -4 -5 여기서 [6,10]에 5를 더하면 -2 -1 0 1 2 4 3 2 1 0 여기서 [2,7]에 2를 더하면 -2 1 2 3 4 6..

• format_list_bulleted 누적 합 알고리즘
• · 2024. 3. 31.
• textsms

분할 정복 중요 테크닉 - 히스토그램에서 가장 큰 직사각형 찾기

1. 문제 1725번: 히스토그램 (acmicpc.net) 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자 www.acmicpc.net 2. 풀이 히스토그램이 주어질때, 찾을 수 있는 직사각형중 넓이가 가장 큰 직사각형을 찾는 문제 위와 같은 경우 다음과 같은 직사각형을 찾을 수 있을 것이다. 히스토그램이 높이 배열 A로 주어질 때, 어떤 구간 [i,j]까지 잡았을 경우, 만들 수 있는 직사각형은 높이가 가장 낮은 min(A)에 구간의 길이 j-i+1을 곱한 값이다. 따라서 가능한 모든 경우에 대해 min..

• format_list_bulleted 분할 정복
• · 2023. 9. 22.
• textsms