Coding Test/Step19. 조합론 (5) 썸네일형 리스트형 [Java] 5단계. 다리 놓기 [1010번] https://www.acmicpc.net/problem/1010예제 입력132 21 513 29예제 출력11567863915문제 접근입력 첫째 줄 : 테스트 케이스 T ~ T번째 줄 : 서쪽 사이트 개수 N, 동쪽 사이트 개수 M(0 출력 각 테스트 케이스에서 조건에 맞게 다리를 지을 수 있는 경우의 수 출력문제 해결서쪽 사이트와 동쪽 사이트가 1:1 매핑이 되어야 함 → 한 사이트가 반대편 사이트에 여러 개 다리 설치 불가서쪽 사이트 수(N) 이기 때문에 결국 mCn의 조합 문제여러 개의 케이스가 주어지기 때문에 미리 dp[30][30]의 배열을 만들고, 규칙을 적용하고 2중 for문으로 점화식 사용dp[i][i] = 1dp[i][0] = 1dp[i][j] = dp[i - 1][j] + dp[i - .. [Java] 4단계. 이항 계수 1 [10872번] https://www.acmicpc.net/problem/11050예제 입력15 2예제 출력110문제 접근이항계수란 주어진 집합에서 원하는 개수만큼 순서없이 뽑는 조합의 개수를 의미순서가 있다는 것은 순열, 순서가 없다는 것은 조합5개 중 2개를 선택(5C2) → 5 * 4 * 3 * 2 * 1 / 3 * 2 * 1 * 2 * 1 = 120 / 12 = 조합 경우의 수는 10개입력 N과 K (1 출력 (5, 2) 이항 계수 출력 문제 해결5개 중 2개를 선택한다는 것은 다음과 같이 볼 수 있음가장 마지막 데이터를 선택 → 이미 1개가 선택되어 4개 중 1개를 선택가장 마지막 데이터를 선택하지 않음 → 4개 중 2개를 선택즉, 5개 중 2개를 선택한 경우의 수 = 4개 중 1개를 선택한 경우의 수 + 4개.. [Java] 3단계. 팩토리얼 [10872번] https://www.acmicpc.net/problem/10872예제 입력110예제 출력13628800예제 입력20예제 출력21문제 접근입력 N (0 12) 출력 N 팩토리얼 출력 문제 해결문제를 푸는 방법은 2가지입력받은 N ~ 1까지 모두 곱하는 반복문 사용재귀 함수 사용반복문 풀이 [메모리 : 14,084 KB / 시간 : 104 ms]public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int sum = 1; for(in.. [Java] 2단계. 녹색거탑 [24723번] https://www.acmicpc.net/problem/24723예제 입력11예제 출력12예제 입력22예제 출력24문제 접근입력 녹색 거탑의 높이 N (1 출력 녹색 거탑의 정상에서 바닥으로 내려오는 경우의 수 출력문제 해결바닥과 근접한 상자 1개당 2개의 경우의 수를 가짐따라서, 규칙을 보면 2^n만큼의 규칙을 보임기존 풀이 [메모리 : 14,016 KB / 시간 : 100 ms]public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); .. [Java] 1단계. 베라의 패션 [15439번] https://www.acmicpc.net/problem/15439예제 입력11예제 출력10예제 입력22예제 출력22예제 입력35예제 출력320문제 접근입력 첫째 줄 : N (1 출력 상의와 하의가 다른 서로 다른 색상의 조합 가짓수 출력문제 해결N * N의 2차원 배열로 나타냄N = 3 이라고 했을 때 i == j가 동일하면 0, 동일하지 않으면 1배열의 총 합 = 서로 다른 색상의 조합 가짓수기존 풀이 [메모리 : 30,676 KB / 시간 : 156 ms]public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); .. 이전 1 다음
