이항 계수2 [9375] 패션왕 신해빈 맨몸으로 갈 수 없으니 최소 1종류 이상의 의류를 착용해야 한다 M 종류의 옷이 3개일 때 우리가 옷을 고르는 경우의 수는 m1 선택, m2 선택, m3 선택, 아무것도 선택 x 총 4가지이다 결론은 M + 1가지의 경우의 수가 존재한다는 것이다 그렇게 의상의 종류만큼 반복하며 특정 종류의 옷 개수 + 1을 곱해야 한다 하지만 답은 1을 빼줘야 하는데, 이는 아무것도 입지 않은 경우의 수를 빼준 것이다 map을 이용하여 옷의 종류를 key로 하였다 조합론 문제이기 때문에 저번에 구현했던 이항 계수 코드를 가져와서 풀었다 그렇게 완성된 코드는 아래와 같다 #include #include #include using namespace std; int T, N; int dp[101][101]; int R; in.. 2022. 8. 29. [1010] 다리 놓기 문제에서 핵심은 '겹치지 않게' 다리를 짓는 것이다 바로 조합을 이용하면 된다 전에 [이항 계수 2]에서 풀었던 동적 계획법 코드를 가져왔다 https://kmyobin.tistory.com/53 [11051] 이항 계수 2 원래는 팩토리얼로 문제를 풀었으나, N의 범위가 커지면서 쓸 수 없게 되었다 그래서 알고리즘 설계 때 배운 DP(동적 프로그래밍)을 떠올리며 문제를 풀었다 ( 시험에서는 틀렸다 ㅡㅡ ) DP(Dynamic P kmyobin.tistory.com 그렇게 완성된 코드는 아래와 같다 #include using namespace std; int T, N, M; int dp[31][31]; int f(int n, int k) { for (int i = 0; i N >> M; printf("%.. 2022. 8. 28. 이전 1 다음
