tose33

https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 1. A와 B에 대해 배열의 요소를 1개 선택, 2개 선택, ... , N개 선택했을때의 누적합을 구한다. 구하는 방법은 cnt개 선택이라면 [arr[0], arr[cnt-1]) 까지의 합 sum을 구하고, 다음 인덱스로 이동하면서 sum에서 arr[i] 값은 더해주고 arr[i-cnt] 값은 빼준다. 이렇게 하면 O..

https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 아이디어를 떠올리는게 쉽지 않은 문제였다. 우선 석순과 종유석을 따로 계산해야 한다. 문제를 푸는데 핵심은 각 길이의 석순,종유석이 몇개인지 카운트해서 누적합을 계산하는 것이다. 예를들어 문제에서 나온 예제의 석순의 길이는 {1,4,2,3,3,3,3} 이다. 각 길이의 갯수를 카운팅하면 다음과 같다. 높이 1 2 3 4 5 갯수 1 1 4 1 0 큰 높이에서 작은 높이로 누적합을 구하면 다음과 같다...

https://www.acmicpc.net/problem/2571 2571번: 색종이 - 3 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net 이전에 푼 문제인데 그때는 브루트포스 O(N^6) 방식으로 풀었다. https://tose33.tistory.com/758 백준 2571. 색종이 - 3 https://www.acmicpc.net/problem/2571 2571번: 색종이 - 3 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색..

https://www.acmicpc.net/problem/2571 2571번: 색종이 - 3 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net 모든 0이 아닌 좌표 (검정 색종이가 있는 좌표)에 대하여 1x1 크기 부터 100x100 크기의 사각형이 만들어 질수 있는지 확인하고, 만들어 진다면 최댓값을 갱신하면 된다. 다른 분들 코드를 봤는데 누적합을 이용한 더 효율적인 풀이 방법이 있었다. 내가 먼저 풀이한 방법은 모든 좌표들에 대하여 O(N^2), 모든 크기에 대하여 O(N^2), 사각형 만들어지는지 여부 O(N^2) 를 확인하기..