목록조합론 (9)
정화 코딩
[C++] 복권 (백준 1359번)
https://www.acmicpc.net/problem/1359 #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); long long f[11]; f[0] = 1; for (int i = 1; i > n >> m >> k; cout.precision(10); int ans = 0; for (int i = k; i 수식은 아래와 같다.시그마 안에 있는 식을 정리하면 아래와 같다.그런데 아래와 같이 구현하면 WA를 받게 된다.for (int i = k; i 답을 이렇게 계산하면 8 7 1 를 입력했을 때 1.02290799..
[C++] 선이 하나 더ㅠㅠ (백준 29727번)
https://www.acmicpc.net/problem/29727 #include using namespace std;long long comb(int n, int r) { if (r > n) return 0; long long ans = 1; for (int i = n; i > n - r; i--) { ans *= i; } for (int i = r; i > 0; i--) { ans /= i; } return ans;}int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, xa, ya, xb, yb; cin >> n >> xa >> y..
EDOC 2024-1 5회차 과제 (동적 계획법 알아보기 3)
090. LCS 2 (백준 9252번) https://www.acmicpc.net/problem/9252 import sysinput = sys.stdin.readlinestr1 = input().strip()str2 = input().strip()len1 = len(str1)len2 = len(str2)dp = [[0 for _ in range(len2 + 1)] for _ in range(len1 + 1)]memo = [[0 for _ in range(len2 + 1)] for _ in range(len1 + 1)]for i in range(1, len1 + 1): for j in range(1, len2 + 1): if str1[i - 1] == str2[j - 1]: ..
EDOC 2024-1 3회차 정모 (조합 알아보기 2)
A. 베라의 패션 (백준 15439번) https://www.acmicpc.net/problem/15439 #pythonimport sysinput = sys.stdin.readlinen = int(input())ans = n * (n - 1)print(ans)(정답) C. 격자상의 경로 (백준 10164번) #pythonimport sysinput = sys.stdin.readlinen, m, k = map(int, input().split())dp = [[0 for _ in range(n + m - 1)] for _ in range(n + m - 1)]ans = 0dp[0][0] = 1for i in range(1, n + m - 1): dp[i][0] = dp[i][i] = 1 for..
EDOC 2024-1 2회차 과제 (조합 알아보기 2)
080. 조약돌 꺼내기 (백준 13251번) https://www.acmicpc.net/problem/13251 import sysinput = sys.stdin.readlinem = int(input()) # 조약돌 색 종류color = list(map(int, input().split())) # 색 별 조약돌의 수k = int(input()) # 뽑는 조약돌의 수n = sum(color) # 전체 조약돌 수ans = 0for x in color: if x >= k: tmp = 1 for i in range(k): tmp *= ((x - i) / (n - i)) ans += tmpprint(ans)오잉 다이나믹도 아니고 조합 구할 필요도 없..
EDOC 2024-1 2회차 정모 (조합 알아보기 1)
A. 다이나믹이 뭐예요? (백준 14494번) https://www.acmicpc.net/problem/14494 #pythonfrom sys import stdin# 점화식 : dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1]mod = 1000000007n, m = map(int, stdin.readline().split()) # n 가로 m 세로dp = [[0 for _ in range(n + 1)] for _ in range (m + 1)]for i in range(1, n + 1): dp[1][i] = 1for i in range(2, m + 1): dp[i][1] = 1 for j in range(2, n + 1): dp[i][..
EDOC 2024-1 1회차 과제 (조합 알아보기 1)
10-1. 조합 알아보기 076. 이항 계수 1 (백준 11050번) https://www.acmicpc.net/problem/11050 from sys import stdin n, k = map(int, stdin.readline().split()) dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)] dp[0][0] = 1 for i in range(1, n + 1): dp[i][0] = dp[i][i] = 1 for j in range(1, i): dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] print(dp[n][k]) 예전에 팩토리얼로 풀었던 문제. 이렇게 점화식을 이용해서 전체 테이블을 다 채워서 푸는 풀이로는 처음 풀..
꾸준히 문제 풀기 - 9월 1, 2주차
9/1. 이항 계수 1 (백준 11050번) https://www.acmicpc.net/problem/11050 #python import sys def fact(num) : ans = 1 for i in range(1, num+1) : ans *= i return ans n, k = map(int, sys.stdin.readline().split()) ans = fact(n) / (fact(k) * fact(n-k)) print(int(ans)) 저번에 풀었던 문제이지만 저번에 풀 때는 함수를 만들어서 하지 않았기 때문에, 이번에는 함수를 만들어서 활용하는 방법으로 풀어봤다. (정답) 9/3. 카드2 (백준 2164번) https://www.acmicpc.net/problem/2164 #python i..