[BOJ] 13900 순서쌍의 곱의 합 - JAVA

1. 문제

13900번: 순서쌍의 곱의 합

---

2. 풀이

ver.1 누적합 사용

2 3 2 4 배열이 있을 때,

3 -> 2*3,

2 -> 2*2 + 3*2 = (2+3)*2,

4->2*4+3*4+2*4 = (2+3+2)*4 를 이용한 방식이다.

따라서 i-1까지의 누적합*현재 수를 sum에 더하면 된다.

public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   int N = Integer.parseInt(in.readLine());
   long[] num = new long[N];
   StringTokenizer st = new StringTokenizer(in.readLine());
   
   long sum = 0;
   long n;
   num[0] = Integer.parseInt(st.nextToken());
   for(int i=1;i<N;i++){
      n = Integer.parseInt(st.nextToken());
      num[i] = n + num[i-1];
      sum += num[i-1]*n;
   }

   System.out.println(sum);
}

 

ver.2 Map 사용

위의 방식보다 조금 더 비효율적인 풀이다.

map에 카운팅시킨 것을 활용해 sum을 구한다.

같은 수가 2개 이상 나온다면 숫자*숫자*경우의 수를 미리 더한다.

그 후 i+1부터 탐색하며 숫자*다음숫자*경우의 수를 더한다.

public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   int N = Integer.parseInt(in.readLine());
   Map<Integer,Integer> map = new HashMap<>();
   StringTokenizer st = new StringTokenizer(in.readLine());

   int num;
   for(int i=0;i<N;i++) {
      num = Integer.parseInt(st.nextToken());
      map.put(num,map.getOrDefault(num,0)+1);
   }

   List<Integer> keyList = new ArrayList<>(map.keySet());
   long sum = 0,val;
   int key;
   for(int i=0;i<keyList.size();i++){
      key = keyList.get(i);
      val = map.get(key);
      if(val>1) sum += (val*(val-1)/2)*key*key;
      for(int j=i+1;j<keyList.size();j++){
         sum += val*map.get(keyList.get(j))*key*keyList.get(j);
      }
   }

   System.out.println(sum);
}

---

3. 결과

한 땀 한 땀 sum을 구하다가 시간초과났다. 그 다음 map을 사용했는데 너무 시간이 많이 걸려서 누적합 방식으로 변경했다.