[백준 / BOJ] 16564 히오스 프로게이머 (누적합 풀이)
문제 출처 : https://www.acmicpc.net/problem/16564 16564번: 히오스 프로게이머 첫째 줄에는 캐릭터의 개수 N, 올릴 수 있는 레벨 총합 K가 주어진다. (1 ≤ N ≤1,000,000, 1 ≤ K ≤ 1,000,000,000) 다음 N개의 줄에는 현재 각 캐릭터의 레벨이 X1, X2, X3, ... , Xn 으로 주어진다. (1 ≤ X www.acmicpc.net N개의 캐릭터로 이루어진 팀이 있다. 이 팀의 팀 레벨은 팀의 가장 작은 레벨을 갖고있는 플레이어의 레벨과 동일하다. 팀의 플레이어의 레벨을 K만큼 올릴 수 있을때, 최대 팀 레벨을 구하는 문제다. 풀이 약간의 아이디어만 있으면 풀리는 문제였다. N과 K의 값이 커서 완전탐색으로 풀경우 시간초과가 나온다. 시..
[백준 / BOJ] 11509 풍선 맞추기
문제 출처 : https://www.acmicpc.net/problem/11509 11509번: 풍선 맞추기 첫 번째 예제 에서 [5,4,3] 을 터트리고 [2,1]을 터트리면 모든 풍선을 터트릴 수 있으므로 최소한 2개의 화살을 필요로 한다. www.acmicpc.net 높이가 같거나 다른 N개의 풍선이 직선에 있다. 화살을 날려 풍선을 터트릴 수 있는데, 한 풍선을 터트릴때마다 화살의 높이가 1만큼 낮아진다. 이때, 모든 풍선을 터트리기위해 필요한 화살의 최소횟수를 구하는 문제다. 풀이 아이디어?로 풀리는 문제였다. 풍선이 최대 1,000,000개 주어지기 때문에, 완전탐색으로는 풀 수 없다. 문제를 풀기위해, 이전에 던져진 화살들의 위치를 기억하는 방식으로 풀었는데, 이러면 O(N)시간복잡도로 문제..
