https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제조건 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이는? 접근방법 시간제한도 타이트하고, 입력값도 크게 주어지길래, 단순히 for문 두번 돌려서 O(n^2) 으로 시간이 걸리게 된다면 당연히 시간초과가 날 것이라고 생각했고, 문득 저번에 이런 비슷한 문제를 푼 경험이 떠올랐다. 2024.03.21 - [Algorithm/구현, 시뮬레이션..

https://www.acmicpc.net/problem/3114 3114번: 사과와 바나나 첫 번째 예제의 경우 불도저가 오른쪽-아래, 오른쪽-아래, 아래로 이동하면 된다. 경로의 아래에 있는 사과 나무의 개수는 3+2+4=9개이고, 위에 있는 바나나 나무의 개수는 3+5=8개이다. www.acmicpc.net 문제조건 아래(↓), 오른쪽(→), 오른쪽아래(↘)로 갈수 있는 불도저가있고, 오른쪽 맨 아래칸까지 이동한다. A(불도저 아래쪽, 사과), B(불도저 위쪽, 바나나) 사과와 바나나의 합의 최댓값의 경우는? 처음 문제를 봤을땐, 탐색을 진행하는 경우의 수인것같아서 BFS로 접근했다. 하지만 이 접근방법은 최소일때 구하기 용이한 방법으로 생각을 좀더 했다. 우선 Brute Force를 떠올렸는데, ..