[Algorithm] 볼링공 고르기

문제

A, B 두 사람이 볼링을 치고 있다. 두 사람은 서로 무게가 다른 볼링공을 고르려고 한다.

볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번부터 순서대로 부여된다.

또한 같은 무게의 공이 여러 개 있을 수 있지만, 서로 다른 공으로 간주한다.

볼링공의 무게는 1부터 M까지의 자연수로 존재한다.

 

예를 들어 N이 5이고 M이 3이며 각각의 무게가 차례대로 1, 3, 2, 3, 2일 때, 각 공의 번호가 차례대로 1번부터 5번까지 부여된다. 이 때, 두 사람이 고를 수 있는 볼링공 번호의 조합을 구하면 다음과 같다.

 

(1번 2번), (1번 3번), (1번 4번) (1번 5번) (2번 3번) (2번 5번) (3번 4번) (4번 5번)

 

결과적으로 두 사람이 공을 고르는 경우의 수는 8가지이다.

N개의 공의 무게가 주어질 때, 두 사람이 볼링공을 고르는 경우의 수를 구하는 프로그램을 작성하시오.

 

입력 조건

첫째 줄에 볼링공의 개수 N, 공의 최대 무게 M이 주어진다.

둘째 줄에 각 볼링공의 무게 K가 순서대로 주어진다.

 

출력 조건

볼링공을 고르는 경우의 수를 출력한다.

 

풀이

이중 반복문을 사용해서 저장된 무게들을 서로 비교해 다른 경우의 수를 계산한다.

그리고 나온 결과에 1/2를 곱한다. (번호가 같은데, 순서만 바뀐 경우 존재)

import java.util.*;

class Main {

  public static void main(String[] args) {
    
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    Integer[] weight = new Integer[n];
    for (int i = 0; i < n; i++) {
      weight[i] = sc.nextInt();
    }
    sc.close();

    Arrays.sort(weight);

    int result = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (weight[i] != weight[j]) result++;
      }
    }

    System.out.println(result / 2);

  } // end main
}

 

다른 풀이

무게에 따른 계수를 한다. 

A가 특정한 무게의 볼링공을 선택했을 때, 이어서 B가 볼링공을 선택하는 경우를 차례대로 계산한다.

1. A가 무게 1을 선택할 때 경우의 수는 1(무게가 1인 공의 개수) * 4 (B가 선택하는 경우의 수)

2. A가 무게 2를 선택할 때 경우의 수는 2(무게가 2인 공의 개수) * 2 (B가 선택하는 경우의 수)

3. A가 무게 3을 선택할 때 2 (무게가 3인 공의 개수) * 0 (B가 선택하는 경우의 수)

 

단계가 거듭되면서, B가 선택하는 경우의 수가 줄어드는 것은 이미 계산 했던 경우는 제외하기 때문이다. (조합)

 

import java.util.*;

class Main {

  public static void main(String[] args) {
    
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    Integer[] weight = new Integer[m+1]];
    for (int i = 0; i < n; i++) {
      int x = sc.nextInt();
      weight[x]++;
    }
    sc.close();

    int result = 0;
    for (int i = 1; i <= m; i++) {
      n -= weight[i];
      result += weight[i] * n;
    }


  } // end main
}