섹션 8. DFS, BFS 활용 7. 조합의 경우수(메모이제이션)

문제

입력

• 첫째 줄에 자연수 n(3<=n<=33)과 r(0<=r<=n)이 입력됩니다.

출력

• 첫째 줄에 조합수를 출력합니다.

입출력 예제

---

풀이방식

이번 문제는 DFS에 대한 문제이다.

---

설계과정

문제 이해는 아래 이미지를 보면 쉽게 이해할 수 있다.

2. R이 0이면 1을 리턴한다.

3. N과 R이 동일하면 1을 리턴한다.

4. 메모리제이션을 위해 2차원 배열을 선언하고, 배열의 값이 0보다 크면 배열[N][R] 값을 리턴한다.

5. 그렇지 않다면 배열에 재귀함수를 각각 호출하여 리턴한다.(DFS(N-1, R-1) + DFS(N-1, R))

---

풀이과정

1. 메모리제이션을 위해 2차원 배열을 선언한다.

2. N이 R과 동일하면 1을 리턴한다.

 

3. R이 0이면 1을 리턴한다.

 

4. 2차원 배열의 값이 0보다 크면 배열[N][R] 값을 리턴한다.

 

5. 그렇지 않다면 배열에 재귀함수를 각각 호출하여 리턴한다.(DFS(N-1, R-1) + DFS(N-1, R))

• 호출 파라미터는 문제를 보면 알 수 있다.

---

더 자세한 설명은 아래 글을 참조해서 확인해보기 바랍니다.

섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 6. 부분집합 구하기(DFS)

섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 6. 부분집합 구하기(DFS)

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.