nnginii

문제https://www.acmicpc.net/problem/14929풀이주어진 수열에서 모든 두 원소 (Ai, Aj)의 곱을 더하는 문제입니다. 단순히 이중 반복문을 사용하면 O(N^2)의 시간 복잡도를 가지게 되어 N의 크기가 100000일 때 비효율적입니다. 이를 줄이기 위해 누적합을 활용하는 방법을 사용합니다.접근각 원소를 순차적으로 탐색하며 현재 원소를 제외한 나머지 원소와의 곱을 빠르게 계산할 방법을 고민했습니다. i번째 원소를 기준으로 (i+1)번째붕터 마지막 원소까지의 합을 구하고 이를 Ai와 곱하는 방식으로 풀이할 수 있습니다. 이를 위해 누적합을 활용하여 각 원소를 기준으로 남은 원소들의 합을 O(1) 연산으로 구할 수 있도록 합니다. 전체 합을 미리 구한 후, 각 원소와 해당 원소 이..

문제https://www.acmicpc.net/problem/5347풀이최소공배수(LCM)는 두 수의 곱을 최대 공약수(GCD)로 나눈 값으로 구할 수 있습니다. 즉, LCM(a,b) = (a*b) / GCD(a,b) 최대 공약수는 유클리드 호제법을 이용하여 효율적으로 구할 수 있습니다. 두 수 a,b에 대해, GCD(a,b) = GCD(b, a%b)로 제귀적으로 계산할 수 있습니다.접근주어진 두 수의 범위가 크므로, 직접 두 수의 배수를 비교하는 방식은 비효율적 입니다. 따라서 유클리드 호제법을 이용하여 최대공약수를 구한 후, 이를 이용해 최소공배수를 계산하는 것이 효과적입니다. long 타입을 사용하여 큰 숫자의 오버 플로우를 방지합니다. 코드import java.util.*;public class ..

문제https://www.acmicpc.net/problem/2014풀이이 문제는 최소힙(Priority Queue)과 중복방지(Set)을 활용하여 해결할 수 있습니다. 초기 소수들을 최소 힙에 삽입하고, 가장 작은 값을 꺼내서 소수들과 곱한 새로운 값을 생성합니다. 중복을 방지하면서 N번째로 작은 값을 찾습니다. 이 방식으로 문제를 해결한다면 중복된 값을 계산하지 않으면서도 작은 값부터 차례로 탐색할 수 있습니다.코드import java.util.*;public class BJ2014 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int k = sc.nextInt(); //(1..