티스토리 뷰
Solved.ac Class 완전정복 프로젝트
Class : 2 ~ 2 ++
링크
https://www.acmicpc.net/problem/11050
11050번: 이항 계수 1
첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\))
www.acmicpc.net
문제
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
접근방법
이항계수란 '이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수'라고 위키 백과는 정의한다. 자연수 n , 정수 k 에 대한 이항계수는 아래의 그림과 같다.
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
즉, 조합이다. 조합 구현을 요구하는 문제임을 인식하고 들어가자.
풀이
위의 공식을 만들면 된다. 나는 두가지 방식으로 구현했다.
코드
1. 반복문을 이용하여 구현
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Main test = new Main();
}
public Main(){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
System.out.println(solution(N,M));
}
public int solution(int N,int K){
int top=1;
int down =1;
for (int i = 1 ; i <= K ; i++){
top *=(N+1-i);
}
for (int i = 1 ; i <= K ; i++){
down *=i;
}
return top/down;
}
}
2. 재귀함수를 이용하여 구현
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Main test = new Main();
}
public Main(){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
System.out.println(solution(N,M));
}
public int solution(int N,int K){
if(K ==0 || N==K){
return 1;
}
return solution(N-1,K) + solution(N-1,K-1);
}
}
결과
재귀함수를 이용할 때에는 입력 범위를 제대로 인지해야한다. 호출 횟수가 비약적으로 늘어나므로, 수치가 클수록 기하 급수적으로 호출횟수가 늘어나니 주의하자.
포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.
더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.
읽어주셔서 감사합니다.
'공부 > 코딩 테스트 준비' 카테고리의 다른 글
[백준] 10816 - 숫자 카드2 JAVA (0) | 2021.09.05 |
---|---|
[백준] 18111 - 마인크래프트 (0) | 2021.09.04 |
[백준] 2869 - 달팽이는 올라가고 싶다 JAVA (0) | 2021.09.03 |
[백준] 11651 - 좌표 정렬하기 2 JAVA (0) | 2021.09.03 |
[백준] 10989 - 수 정렬하기 3 JAVA (0) | 2021.09.02 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 아기상어미워
- value annotation
- 재귀
- db
- 플루이드 와샬
- 브루트포스
- 프로그래머스 문제정복
- DP
- 실패일기
- java
- 자바
- JNDI연동
- Database
- 9019
- 백준
- 파이썬
- 그래프 탐색
- 아기상어나쁜상어
- looker core
- looker instance 접속
- 유클리드-호제법
- BFS
- Python
- DFS
- dml
- 코딩테스트
- Spring
- 프로그래머스
- 카카오
- 하루 회고
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
글 보관함