섹션 8. DFS, BFS 활용 8. 수열 추측하기

문제

• 가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다.
• 예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다.
• N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오.
• 단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.

입력

• 첫째 줄에 두개의 정수 N(1≤N≤10)과 F가 주어진다.
• N은 가장 윗줄에 있는 숫자의 개수를 의미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하이다.

출력

• 첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다.
• 답이 존재하지 않는 경우는 입력으로 주어지지 않는다.

입출력 예제

---

풀이방식

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

---

설계과정

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

트리 구조로 정리해보면 맨 마지막에 각 숫자별로 몇 번 더해졌는지 횟수를 알 수 있다.

이 횟수들을 수열의 각 값과 곱하면 가장 밑에 있는 값이 나온다.

이 때, 이 횟수들을 앞전에 배운 콤비네이션으로 사용하면 문제를 풀 수 있다.

1. arr 배열에 콤비네이션 값들을 저장한다.

2. 1부터 N까지 돌면서 배열 P에 수열에 해당하는 값들을 넣는다.

3. 수열의 해당 숫자가 중복되지 않았다면 ch 배열에 1을 넣어주고 P[L] 에 수열을 넣어준다.

4. 재귀함수 DFS를 호출한다.

5. 이 때 DFS의 파라미터는 L+1과 sum+(P[L] * arr[L]) 으로 넣어준다.

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

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

---

풀이과정

1. 각 변수들을 선언한다.

• 메모이제이션을 위해 2차원 배열 dy[ ] 을 선언한다.
• 중복수열이 아니기에 중복을 체크할 배열 ch[ ] 을 선언한다.
• 콤비네이션을 저장할 배열 arr[ ] 을 선언한다.
• 수열을 저장할 배열 P[ ] 을 선언한다.
• 재귀가 더 돌지 않게 하기 위해 flag 를 선언한다.

2. 먼저 arr 배열에 콤비네이션 들을 저장하기 위해 combi 메소드를 작성한다.

• 콤비네이션이 NC0 ~ NCN 까지 만들어지고, 이를 arr에 저장해야 한다.
• 나중에 수열 배열 P[ ] 와 arr 배열의 값을 각각 곱하기 위해 만든다.
• i번째 수열과 그 수열이 더해진 횟수를 곱해서 가장 밑에 있는 수를 찾기 위함이다.

3. 배열 dy[ ][ ] 가 0보다 크다면 그 값을 그대로 리턴한다.

• 메모리제이션에 이미 저장된 값이 있다는 의미이므로 그 값을 사용하기 위해 작성한다.
• 예를 들어 3C2 값이 5임을 한번 구했고, 나중에 이 값이 또 다시 쓰여야 한다고 가정해보자.
• 해당 값을 처음부터 다시 구하는 것이 아니라 이미 만들어진 값을 사용해서 처리 시간을 줄일 수 있다.

4. N이 R과 동일하거나 R이 0이면 1을 리턴한다.

 

5. 그렇지 않다면 combi 메소드에 (N-1, R-1) + combi(N-1, R) 파라미터를 넣어서 dy[ ] 배열에 값을 저장한다.

• 메모리제이션을 위한 작업이다.

6. 이제 DFS 메소드를 작성해보자.

 

7. L이 N과 동일하다면 sum이 F와 동일한지 확인한다. 만약 동일하다면 그대로 결과를 출력한다.

• L이 N과 동일하다는 것은 수열이 완성되었다는 의미이다.
• 누적값인 sum이 가장 밑에 있는 수 F와 같다면 원하는 결과를 찾은 것이므로 P 배열에서 각 수열의 값들을 출력한다.

8. 원하는 결과를 찾았다면 flag 변수에 true를 넣는다. 

• 답을 찾았으니 더 이상 재귀함수를 돌리지 않기 위해서이다.

9. 수열이 미완성이라면 1부터 N까지 도는 for 문을 작성한다.

• 이 때, i 는 각 수열의 숫자를 의미한다.
• 수열의 숫자는 1부터 N까지 존재하므로 범위를 그에 맞게 잡아준다.

10. 중복된 수열이 아니라면 ch[ ] 배열에 1을 넣어주고 P[L] 에 i 값을 넣어준다.

• i 는 수열의 숫자이므로, P[L] 번째 배열에 수열을 넣는 과정이다.

11. L+1과 sum+(P[L] * arr[L]) 으로 파라미터를 넣어서 재귀함수를 호출한다.

• 수열에서 L번째 수와 해당 수가 더해진 횟수를 곱해서 누적값을 sum에 저장한다.

12. 다음 탐색을 위해 ch[ ] 배열에 값을 0으로 넣어준다.

• 다음 레벨 탐색을 위해 이전에 탐색했던 수에 대해 방문 기록을 없애주는 과정이다.

13. DFS(0, 0) 으로 재귀함수를 시작하며 결과를 확인한다.

 

---

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

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

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

---

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