그리디6 [백준][그리디] 18310 안테나 c++ 구현 https://www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 문제 문제 풀이 최적부분 구조는 정렬했을 때 크기가 짝수이면 중간 index-1 크기가 홀수이면 가운데 중간 index이다. 코드 구현 #include #include #include #include using namespace std; vector arr; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, num, i, sum=.. 2024. 3. 19. [백준][그리디] 11501 주식 c++ 구현 목차 https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 문제 문제 풀이 시 주의해야 할점 이중반복문을 돌리게 되면 시간 복잡도가 O(N^2)이 나와 시간초과로 틀리게 된다. 따라서 전처리를 통해 자기보다 큰 것이 없는지 있는지 정해주어 풀면시간복잡도가 O(N)으로 풀리게 도힌다. 문제 풀이 오늘보다 뒷날에 주가가 더 큰 것이 있다. 매수한다. 오늘보다 뒷날에 더 큰 것이 없다. 주식이 있다면 판다. 주식이 없다면 나둔다. 이런식의 최.. 2024. 3. 16. 이전 1 2 다음 728x90
