[백준 / BOJ] 1124 언더프라임
문제 출처 : https://www.acmicpc.net/problem/1124 1124번: 언더프라임 자연수 X를 소인수분해하면, 곱해서 X가 되는 소수의 목록을 얻을 수 있다. 예를 들어, 12 = 2 × 2 × 3이다. 1은 소수가 아니다. 어떤 수 X를 소인수분해 해서 구한 소수의 목록의 길이가 소수이면, www.acmicpc.net 두 양의 정수 A,B가 주어졌을때, A,B사이의 언더프라임을 구하는 문제다. 여기서 언더프라임은 정수의 소인수분해의 결과로 나온 소수들의 길이가 소수인 수를 의미한다. 풀이 에라토스테네스 채를 이용해서 A,B사이의 모든 소수들을 구해놓은 후, A,B사이에 있는 임의의 정수 X가 언더프라임인지 확인하는 방식으로 푸는 문제다. 이 때, 시간이 애매할거 같아서, 연산을 빠..
[백준 / 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)시간복잡도로 문제..
