[수학] 조합 공식 / 백준 10986

https://www.acmicpc.net/problem/10986

10986번: 나머지 합

 

백준 10986번을 풀면서 새롭게 배운 공식을 써보려고 한다.

일단 이전에 합 배열 문제에서 구간합을 구하는 방법을 배웠다.

 

나머지 합 문제에서 콤비네이션 공식이라는걸 쓰는데 매우 신기하고

다음에도 유용하게 쓸 것 같아서 작성하려고 한다.

 

 

nCr

서로 다른 n개 중에서 겹치지 않도록 r개를 선택하는 방법의 수

 

 

 

예를들어 20명중 2명을 뽑는다고 하면

경우의 수는 190이 나온다.

 

이를 보면 더 이해가 쉬울것이다.

 

 

 

나도 영상을 보고 이해를 했다.

수학에 대해 이해가 많이 필요하겠구나 생각을 하였다..

 

import java.util.Scanner;

public class Main {
    private void solution() throws Exception {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();

        long[] arr = new long[N];
        long[] C = new long[M];
        long result = 0;

        arr[0] = sc.nextInt();
        for(int i = 1; i < N; i++)
        {
            //합배열을 구한다!
            int input = sc.nextInt();

            arr[i] = arr[i-1] + input;
        }

        for(int i = 0; i < N; i++)
        {
            //합배열을 나머지 값으로 초기화한다.
            //합배열중에 나누어 떨어지는 수를 구한다.
            int remainder = (int)(arr[i] % M);

            if (remainder == 0) result++;

            C[remainder]++;
        }

        for (int i = 0; i < M; i++)
        {
            if(C[i] > 0) {
                //경우의 수 구하기
                //나머지 연산중 2개를 뽑아야 하므로
                result += (C[i] * (C[i] - 1)) / 2;
            }
        }

        System.out.print(result);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

이 문제를 풀었을 때 진짜 재밌었다.. 캬..

 

int 형식으로 풀었는데 런타임 에러가 나서 long으로 변경 후 맞았다..

다들 형식에 주의하자!