여사건을 이용한 경우의 수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

DP가 불가능할 때 특정 위치 (x,y)로 이동하는 경우의 수를 구하는 다른 방법

SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 나이트가 (i,j)에 있을때, (i+1,j+2), (i+2,j+1) 둘 중 하나로만 움직일 수 있다고 하자. x,y가 주어질 때, (0,0)에서 출발하여 (x,y)로 이동할 수 있는 경우의 수는? dp[y][x] += dp[y-1][x-2], dp[y][x] += dp[y-2][x-1]로 구할 수 있을 것 같은데 X,Y가 106까지라서 메모리도 안되고 O(N2)이라 시간복잡도도 안된다 나이트가 (i,j)에서 이동하는 방법이 (i+1,j+2), (i+2,j+1) 2가지만 있다는 것을 생각한다면... (0,0)에서 (..

  • format_list_bulleted 조합론
  • · 2024. 4. 5.
  • textsms

경우를 나눠서 생각하면 최적해로 도달하는 경이로운 그리디 알고리즘(전구와 스위치, 전구 상태 바꾸기)

1. 문제 2138번: 전구와 스위치 (acmicpc.net) 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 2. 풀이 핵심 해법은 0번 전구를 누를 수 없다고 할 때, 1번부터 n-1번까지 눌러봐서 원하는 상태에 도달할 수 있는지 체크하고 다음은 0번 전구를 반드시 누를때, 1번부터 n-1번까지 눌러봐서 원하는 상태에 도달할 수 있는지 체크해본다. 둘다 불가능하면 바꿀수 없는 것일테고, 하나라도 가능하다면 최소로 누른 횟수가 정답이 될 것이다. ------------------..

  • format_list_bulleted 그리디 알고리즘
  • · 2023. 9. 7.
  • textsms

모든 부분집합 원소의 곱의 합을 구하는 공식이 있다고?

1. 문제 9375번: 패션왕 신해빈 (acmicpc.net) 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 2. 풀이 경우의 수가 바로 안나오기는 한디... 경우를 나눠서 생각해보면 hat headgear sunglasses eyewear turban headgear headgear에 2가지 있고 eyewear에 1가지 있는데.. headgear에서 1가지를 뽑는 경우의 수 = 2가지 + eyewear에서 1가지 ..

  • format_list_bulleted 확률론 알고리즘
  • · 2023. 8. 20.
  • textsms

integer partition 문제 2 - m개 이하의 수만 사용해서 합이 k가 되도록 만드는 경우의 수 구하는 다이나믹 프로그래밍

1. 문제 15992번: 1, 2, 3 더하기 7 (acmicpc.net) 15992번: 1, 2, 3 더하기 7 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. 단, 사용한 수의 개수는 m개 이어야 한다. www.acmicpc.net 2. 풀이 저번엔 사용 개수의 제한 없이 합을 n으로 만드는 방법을 배웠다면.. https://deepdata.tistory.com/951 합이 k가 되는 경우의 수 구하는 다이나믹 프로그래밍 익히기(구성이 같은데 순서가 다르면 같은 1. 문제 9095번: 1, 2, 3 더하기 (acmicpc.net) 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 ..

  • format_list_bulleted 다이나믹 프로그래밍
  • · 2023. 8. 2.
  • textsms