프로그래밍 공부 노트

https://www.acmicpc.net/problem/16395 16395번: 파스칼의 삼각형 파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행 www.acmicpc.net 파스칼의 삼각형의 n번째 행 k번째 열의 값을 2차원 배열 tri에 대해 tri[n][k]에 저장한 뒤 출력한다. 이 때 tri[n][k] = tri[n - 1][k] + tri[n - 1][k - 1]이다. #include #define MAX_N 30 int main() { // n, k: 이항계수를 구할 값, tri[n][k] = nCk int n, k, tri[MAX_N + 1..

https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 파스칼의 삼각형 법칙에 따라 이항계수 nCk는 k가 0 혹은 n일 때 1, 그 외의 경우에는 (n - 1)C(k - 1) + (n - 1)Ck이다. #include #define MAX_N 1000 #define MOD 10007 int main() { // N, K: 이항계수 상수 int N, K; // ans[n][k]: 이항계수 nCk short ans[2][MAX_N + 1] = {{ 0, }}; // 문제의 조건을 입력받은 뒤 파스칼의 삼각형을 이용해 이항 ..

https://www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 파스칼의 삼각형 법칙에 따라 이항계수 nCk는 k가 0 혹은 n일 때 1, 그 외의 경우에는 (n - 1)C(k - 1) + (n - 1)Ck이다. #include #define MAX_N 10 int main() { // N, K: 이항계수 상수, ans[n][k]: 이항계수 nCk int N, K, ans[MAX_N + 1][MAX_N + 1] = {{ 0, }}; // 문제의 조건을 입력받은 뒤 파스칼의 삼각형을 이용해 이항 계수를 계산 scanf("%d %d", &..

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net k개의 수 중 6개의 수를 kC6번 골라 각각 오름차순으로 출력하는 문제이다. 이 때 입력이 정렬된 상태로 주어지므로 수를 고른 뒤 따로 정렬할 필요 없이 순서대로 출력하면 된다. #include #define MIN_K 6 #define MAX_K 12 // len: 로또 번호의 개수, arr: 각 로또 번호 // picks: 로또 번호 후보 중 로또로 예측되는 번호 int len, ..

https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 문제의 답 중 가장 큰 수 100C50은 100891344545564193334812497256은 대략 10^31로, 64비트로 나타낼 수 있는 범위를 초과한다. 따라서 파스칼의 삼각형 기법을 사용할 경우, 자바나 파이썬에 존재하는 BigInt을 구현해서 문제를 풀어야 한다. #include #define MAX_N 100 #define MAX_LEN 30 #define MOD 10 // 조합의 결과를 저장 bool visit[MAX_N + 1][MAX_N + 1]; char C[MAX_N + 1][MAX_N +..

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 동쪽에 있는 M개의 사이트 중 N개의 사이트를 골라야 하고, 고르는 순서는 상관이 없으므로 주어진 문제는 조합 문제로 볼 수 있다. N과 M의 범위가 30 이하이므로, 파스칼의 삼각형을 이용해 가능한 모든 경우를 탐색한 뒤 테스트 케이스를 진행하면 편하다. #include #define MAX_N 30 #define FOR(i, a, b) for(i = a; i < b; i++) // tri[N]..