728x90 조합론6 [python] 백준 16565 N 포커 https://www.acmicpc.net/problem/16565 문제 해결DP를 이용해 n개중 m개를 뽑았는데 그중 k개 종류가 나올 경우의 수를 dp[m][k]라고 정의한다.dp[0][0]은 1로 정의그러면 $ dp[i][j] = \sum_{k=0}^{3} \binom{4}{k} \times dp[i-k][j-1]$ 이후 포카드가 나올 수 있는 경우의 수를 계산하기 위해idx (포카드 나오는 개수)$ ans += \binom{13}{idx} * dp[n-4*idx][13-idx]$ CODEimport sysinput = sys.stdin.readlineimport mathmod = 10007def combination(n, r): return math.factorial(n)//(math... 2024. 5. 23. [python] 백준 1328 고층 빌딩 https://www.acmicpc.net/problem/1328 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 문제 해결 dp를 써야겠다라는 생각이 드는데 어떻게 써야할지 고민이 되는 문제 n이 1이상 100이하이기 때문에 삼 중 반복문을 써도 괜찮다. dp[i][j][k]를 i개의 빌딩이 있을 때 왼쪽에서 보면 j개 오른쪽에서는 k개 보이는 배열가지수라고 하자. 그러면 dp[1][1][1] =1 이 된다. 가장 기본 값 i-1개의 빌딩이 배열되어있다고 하자. 이제 빌딩 하나를 더 세워 dp[i][j][k.. 2023. 5. 8. [python] 백준 17471 게리맨더링 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 문제 해결 삼성 A형 기출문제 딱 봐도 완전탐색 문제이다.(2 ≤ N ≤ 10, 1 ≤ 구역의 인구 수 ≤ 100) 문제는 combination을 사용하여 모든 경우의 수를 다 고민을 해야하나인데... 맞다. 1개부터 n//2 개까지 선거구를 뽑은 다음 다 연결 되었는지 확인하고 나머지 선거구끼리도 모두 연결되었는지 확인해야한다. 모두 연결이 되면 두 집단의 인구 차이를 이전과 비교해서 작은 값을 저장한다. 삼성은 i.. 2023. 4. 26. [python] 백준 6603 로또 https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 문제 해결 combination(조합) 라이브러리만 쓸 줄 알 면 쉬운 문제 for문 반복으로 출력하면 된다. CODE from itertools import combinations import sys input = sys.stdin.readline while 1: S = list(map(int, input().split())) if S[0] == 0:break for comb in c.. 2023. 1. 12. 이전 1 2 다음 728x90
