5.볼링공 고르기

📍 문제 설명

A, B 두 사람이 볼링을 치고 있습니다. 두 사람은 서로 무게가 다른 볼링공을 고르려고 합니다. 볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번부터 순서대로 부여됩니다. 또한 같은 무게의 공이 여러개 있을 수 있지만, 서로 다른 공으로 간주합니다. 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재합니다.

문제

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

입력 조건

• 첫째 줄에 볼링공의 개수 N, 공의 최대 무게 M이 공백으로 구분되어 각각 자연수 형태로 주어집니다.
  (1 <= N <= 1,000, 1 <= M <= 10)
• 둘째 줄에 각 볼링공의 무게 K가 공백으로 구분되어 순서대로 자연수 형태로 주어집니다.
  (1 <= K <= M)

출력 조건

• 첫째 줄에 두 사람이 볼링공을 고르는 경우의 수를 출력합니다.

입력 예시

5 3
1 3 2 3 2

출력 예시

8

💡 접근

공의 무게가 다를 경우에만 고를 수 있도록 구현하면 된다.

 

책에서는 2번째 코드와 같이 수학적 식을 이용하여 풀었음

 

i = 1 부터 볼링공의 무게까지 for문을 돌린다.

[1,3,2,3,2]

현재 볼링공의 갯수에서 A가 i = 1 무게를 선택하는 경우를 제외하고 B가 나머지를 선택하는 경우의 수를 곱한다.

(1,3) (1,2) (1,3) (1,2)

현재 볼링공의 갯수에서 A가 i = 2 무게를 선택하는 경우를 제외하고 B가 나머지를 선택하는 경우의 수를 곱한다.

(3,1) (3,2) (3,2) (3,1)

 

👩‍💻 코드

import java.util.*;

public class Main {

    public static int solution(int n, int m, int[] arr) {
        int answer = 0;

        for(int i = 0; i < arr.length; i++) {
            for(int j = i+1; j < arr.length; j++) {
                if(arr[i] != arr[j]) answer++;
            }
        }

        System.out.println(answer);

        return answer;
    }

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);

        int[] arr = {1,5,4,3,2,4,5,2};

        Arrays.sort(arr);

        solution(8, 5 , arr);

    }

}

import java.util.*;

public class Main {

    public static int n, m;
    // 1부터 10까지의 무게를 담을 수 있는 배열
    public static int[] arr = new int[11];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            arr[x] += 1;
        }

        int result = 0;

        // 1부터 m까지의 각 무게에 대하여 처리
        for (int i = 1; i <= m; i++) {
            n -= arr[i]; // 무게가 i인 볼링공의 개수(A가 선택할 수 있는 개수) 제외
            result += arr[i] * n; // B가 선택하는 경우의 수와 곱해주기
        }

        System.out.println(result);
    }
}