8/12 (목) 자바 코딩 스터디

2618	경찰차
9251	LCS
10164	격자상의 경로
2839	설탕 배달
1010	다리 놓기

1010번 다리 놓기

강 서쪽에서 동쪽으로 다리를 잇는 프로그램
다리끼리는 서로 겹쳐질 수 없다.

결국에는 강 동쪽의 구역(M) 중 강 서쪽의 구역(N)만큼을 순서 상관 없이 뽑는 경우의 수 를 출력하는 프로그램이다.

첫 번째는 간단 수학식으로 해결해 보았다.

1. 다이나믹 프로그래밍

C(3, 2) = c(2, 1) + c(2, 2)
= C(1, 0)+C(1, 1) + C(1, 1)+C(1, 2)

C(M, N) = C(M-1, N-1) + C(M-1, N)
nCr = n-1Cn-1 + n-1Cn;

    public static int buildBridge2(int n, int r) {
        if (n == r) {
            return 1;
        }

        if (r == 1) {
            return n;
        }

        if (cache[n][r] != -1) {
            return cache[n][r];
        }

        cache[n][r] = buildBridge2(n - 1, r - 1) + buildBridge2(n - 1, r);

        return cache[n][r];
    }

2. 단순 계산하는 방법

nCr = n!/((n-r)! * r!) 을 이용

public static long fac(int n) {
        if (n <= 1) {
            return 1;
        }
        return n * fac(n - 1);
    }

    // nCr = n! / ((n-r)! * r!);
    public static long calNCR(int n, int r) {

        System.out.println(fac(n));
        long nCr = fac(n) / fac(n - r);
        nCr /= fac(r);
        return nCr;
    }

M개 중에서 N개 순서를 생각하지 않고 뽑기

재귀 없이?

2839번 설탕 배달

sugar //5

#수학식
남은 사탕을 3으로 나눈다

그다음 개수가 맞아 떨어지면 종료

아니면 5개짜리 묶음을 하나 해제하고
3개짜리로 다시 묶는다

5개 짜리 묶음의 값이 -1이라면
종료

#DP
Arrays.fill(dp, 100000);
dp 를 100000로 다 초기화

LCS
알고리즘

백트래킹 방식

10164번 격자상의 경로

9251번 LCS

2618 경찰차