알고리즘 문제풀이/백준134 [백준 11051] 이항 계수 2 www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이항계수를 구하는 문제이다. nCk = n!/k!(n-k)!이지만 n과 k가 1000까지 입력을 받기 때문에 저 식대로 계산하면 오버플로우가 발생한다. 그래서 파스칼의 삼각형을 사용하여 구해준다. 파스칼의 삼각형은 dp를 사용해서 구한다. nCk = dp[i][j] if j=0 or i=j then 1 else dp[i][j] = dp[i-1][j-1] + dp[i-1][j]로 식을 세울 수 있다. #include using namespace std; int dp[1001][100.. 2020. 12. 23. [백준 2004] 조합 0의 개수 www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 조합에서 끝자리 0의 개수를 구하는 문제 2와 5의 개수 중 작은 값을 리턴하면 되는 쉬운 문제이나 값의 범위가 long long이므로 while문을 돌려서 모두 확인하면 시간초과가 발생할 것이다. 그래서 사용하는 방법! n!에서 2의 개수와 5의 개수를 구할 것인데 다음과 같은 방법을 사용한다. n=10이라 가정하면 1 2 3 4 5 6 7 8 9 10 을 곱한 값이 10!이다. 이 때 2의 개수를 찾고 싶다면 10을 2의 제곱수로 나눈값을 더해주면 된다. 1. 10까.. 2020. 12. 23. [백준 1929] 소수 구하기 www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 에라토스테네스의 체를 사용하여 구하면 쉽게 구한다. #include using namespace std; int m, n; bool arr[1000001] = { false, }; void eratos(int len) { arr[1] = true; for (int i = 2; i 2020. 12. 22. [백준 17281] 야구 www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 야구 게임 구현이다. 1. dfs를 이용해서 타자 순서를 정하고 2. 정해진 순서대로 게임을 진행해서 점수를 계산한다. 1번 타자는 4번 순서로 고정이고 나머지 타자들 순서만 배치한다. 게임 진행 시엔 공을 친 결과에 따라 ground 배열값과 결과 값이 변한다. 0이면 out수만 증가 1이면 3루에 있던 사람 수 만큼 점수 증가, 나머지 루에서 한칸씩 이동 2와 3도 마찬가지이고 4의 경우 모든 루에 있던 사람들이.. 2020. 12. 22. 이전 1 ··· 15 16 17 18 19 20 21 ··· 34 다음
