모각코 테스트

링크

개요

문제에서 핵심

0보다 크고, 30보다 작거나같은 두 정수에대해서 적절한 조합값을 구하는 방법을 코드로 구현하기.

난이도

solve.ac 난이도 : 실버5
개인 난이도 : 2/5

문제에서 어려움

1. 어떻게 조합을 코드로 구현할 것인가.

   기존의 잘알려진 조합식인 \(\binom{n}{k} = n!/(n-r)!r!\)
   을 사용할 경우 문제가있다. (이는 문제에서 제공하는 테스트 케이스의 마지막 경우에서도 확인 가능하다)
   M값이 30일경우를 가정하면 조합 계산을 위해서 30!을 구해야한다. 이는 int의 표현 가능 범위를 벗어난다.

해결법
구글링으로 파스칼의 삼각형에 해당 공식을 찾을 수 있었다. \(\binom{n}{k} = \binom{n-1}{k-1}+\binom{n-1}{k}\)
해당 공식을 이용하면 30!같은 큰수를 구할 필요가 없이 문제를 해결 가능하다.

특정 조합값을 알기위해 더 작은 조합값 두개를 알아야하므로

1. 0C0부터 30C30 까지 조합을 저장할 31*31 2차원 배열을 선언한다.
2. 동적 계획법을 이용하여 모든 배열을 채운다.

해당방식을 통해 모든 값을 구한 후, 각 케이스마다 필요한 조합값을 가져가는 형태로 구현할 것이다.

코드

//0C0부터 30C30 까지의 값으로 2차원 배열을 채우는 코드.  

public static int[][] arr = new int[31][31]; //배열

public static int main(String args[]){
 for(int i = 0; i<=30; i++){
      arr[i][i] = 1;
      arr[i][0] = 1;
    }
    //기존의 값을 알고있는 두수를 이용해서 다음 수를 구해야하기에 기본적으로 파악가능한 nC0, nC30 같은 수는 미리 배열에 채운다.

    for(int i = 1; i<30; i++){
      for(int j =1 ; j<i; j++){
        arr[i][j] = arr[i-1][j-1]+arr[i-1][j];
      }
    }
    //파스칼의 삼각형 공식을 이용해 배열을 채워나간다 (동적 계획법)
}

이문제 풀이에 필요한 지식.

보완해야 할 부분.

다른사람 코드와 비교