두 팀중 적어도 한 팀이 소수만큼 점수를 얻을 확률

1344번: 축구  90분간 이루어지는 축구 경기를 5분 간격으로 나눈다. 처음 간격은 처음 5분, 두번째 간격은 그 다음 5분... 각 간격에서 A,B팀이 각각 득점할 확률이 주어진다 각 간격에서 A,B팀은 각각 많아야 한골씩 득점할 수 있다 경기가 끝났을 때 적어도 한 팀이 소수로 득점할 확률은? ------------------------------------------------------------------------------------------------------------------------------------ 5분씩 간격이 나눠지고 전체 경기 시간은 90분이므로 총 18간격씩 이루어진다 각 간격에서 두 팀은 독립적으로 최대 1골씩 넣을 수 있다 dp[i][a][b] = i번째 간..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 3. 2.
• textsms

카탈란 수(Catalan numbers) 공부하기

1. 카탈란 수 n = 0,1,2,3,...에 대하여 다음과 같은 수열 1,1,2,5,14,42,132,429,1430,4862,16796,58786,.... 0이상의 n에 대하여 카탈란 수 $C_{n}$는 다음과 같은 재귀적 관계를 만족한다.  $$C_{0} = 1, C_{n} = \sum_{i = 1}^{n} C_{i-1}C_{n-i}$$  이는 다음과 같이 정리할 수 있고  $$C_{0} = 1, C_{n} = \frac{2(2n-1)}{n+1}C_{n-1}$$  점화식을 풀면 다음과 같이 일반항을 도출할 수 있다.  $$C_{n} = \frac{1}{n+1} * \binom{2n}{n}$$   2. 응용 1) Dyck word n개의 X와 n개의 Y로 이루어진 문자열 중 처음부터 하나씩 셌을때 Y의 개수가 ..

• format_list_bulleted 조합론
• · 2025. 2. 25.
• textsms

정수 n을 k개의 자연수로 분할하는 방법의 수

10772번: π-day n개의 파이를 k명의 사람에게 분배하는데 각 사람은 적어도 1개의 파이를 받고, 앞 사람보다 적게 받을 수는 없다 예를 들어 7개의 파이를 5명에게 분배할려면 1 1 1 1 3 1 1 1 2 2 는 유효하지만 2 1 1 2 1은 유효한 경우가 아니다 가능한 방법의 수는? -------------------------------------------------------------------------------------------------------------------------------------------- dp[i][j][x]를 i번째 사람에 j개 분배하고 남은 개수가 x개라고 할때 방법의 수라고 하면 O(N^4)에 해결할 수 있다 처음에 0번 사람에게 j개를 분배하..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 2. 18.
• textsms

여사건을 이용한 경우의 수1 - 특정 수를 포함하는 부분집합 구하는 법

20214번: Binary Seating (acmicpc.net)  두 강의실 0번과 1번에 n명의 학생이 1/2의 확률로 선택하여 입장할때,  1번 강의실에서 모든 시험이 끝날 때까지 걸리는 시간의 기댓값을 구하는 문제 걸리는 시간을 X라고 한다면...? 예를 들어 학생이 5명이고 각각 t = 1,4,5,2,3 만큼 시험을 보고 떠난다고 할때, 가능한 X = 1,2,3,4,5이다. 그러므로 E(X) = 1*P(X = 1) + 2*P(X = 2) + 3*P(X = 3) + 4*P(X = 4) + 5*P(X = 5) P(X = 1)은 어떻게 구할까? t = 1인 학생이 1번 강의실에 들어간 경우 (1) P(X = 2)는 어떻게 구할까? t = 2인 학생이 1번 강의실에 들어간 경우 (2) t = 1인 학생..

• format_list_bulleted 조합론
• · 2024. 8. 23.
• textsms

m면체 주사위 n개를 굴려서 나올 수 있는 경우의 수를 구하는 방법

3886번: Expected Allowance (acmicpc.net)  m면체 주사위 n개를 굴려서 나온 숫자의 합에 컷백 k를 뺀 값만큼 지폐를 받는다고 할 때, 받을 수 있는 지폐 수의 기댓값 이때, k 이하의 수가 나온다면 최소 1장은 받는다 예를 들어 6면체 주사위 2개를 굴리면? 가능한 숫자의 합은 1부터 12까지인데 모든 경우의 수는 36가지이고 숫자의 합이 2인 경우의 수는 (1,1)로 1가지 3인 경우의 수는 (1,2), (2,1)로 2가지 4인 경우의 수는 (1,3), (2,2), (3,1)로 3가지 k = 3이면 지폐를 1가지 받는 경우의 수는 숫자의 합이 2, 3, 4 3가지 경우에 가능하다. 따라서 지폐 1가지 받는 경우의 수는 1+2+3 = 6가지  그러면 먼저 m면체 주사위 n..

• format_list_bulleted 조합론
• · 2024. 8. 17.
• textsms

경기장 일렬 좌석에 앉을 때 사람을 지나치지 않고 전부 앉는 방법의 수

29313번: Стадион (acmicpc.net)  일렬로 된 N개의 좌석이 있는데 사람이 양쪽으로 들어가서 좌석에 앉을 수 있다고 할때,  어떤 사람이 이미 앉은 사람을 지나치지 않고 N명이 모두 앉는 방법의 수를 구하는 문제 예를 들어 3명이 앉는다고 해보면 이렇게 4가지가 있다    N개의 자리가 있을 때 _ _ _ _ _ _ ... 첫번째 자리에 먼저 앉으면 1 _ _ _ _ _ ... 나머지 N-1개의 자리는 고정적으로 2,3,4,5,6,... 으로 1가지 = N-1C0가지 결정된다 두번째 자리에 먼저 앉으면 _ 1 _ _ _ _ .... 1의 왼쪽 자리 _ 를 N-1명중 1명을 결정시키면 1의 오른쪽은 무조건 자동으로 결정되므로... N-1C1가지 왜냐하면 1의 왼쪽에 3을 앉히면 3 1 ..

• format_list_bulleted 조합론
• · 2024. 7. 26.
• textsms