문제

다리놓기

풀이

조합과 관련한 문제인데 조금만 응용이 되서 나오면 엄두가 안난다 상상력이 부족한것 같다. 이 문제는 하나라도 많은 스팟이 있는 부분에서 적은 경우의 수 부분을 선택하야 가장 많은 다리를 놓을 수 있다 ( 겹치지 않고 )
겹치게 도는 경우는 팩토리얼 연산을 사용하게 될 것이다

	public static int[][] bottomUp() {
        int[][] dp = new int[30][30];
        for (int i = 0; i < 30; i++) {
            dp[i][i] = 1;
            dp[i][0] = 1;
        }

        for (int i = 2; i < 30; i++) {
            for (int j = 1; j < 30; j++) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }
        return dp;
    }

팩토리얼 연산을 했을때처럼 모든 배열에 초기 값을 셋팅해준다
0번째 열과 가장 마지막 열은 모두 1인데 이것은 아래의 링크에서 자세하게 설명된다
진작 이런걸 생각해냈다면 참 좋을거같다

전체코드

전체 코드

Reference

• https://en.wikipedia.org/wiki/Binomial_coefficient
• https://ko.wikipedia.org/wiki/%ED%8C%8C%EC%8A%A4%EC%B9%BC%EC%9D%98_%EC%82%BC%EA%B0%81%ED%98%95