문제 유형
가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다.
예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다.
N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오.
단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.
필요자료구조
int n // (수열 갯수),
int total // (정답 값),
int b[] // (수열 추측하기 공식 값 배열),
int p[] // (모든 순열의 경우의수),
int ch[] // (중복된 순열을 배제하기 위함),
int fibo[][] // (메모이제이션),
int L // (현재 레벨),
int sum // (현재 레벨의 sum 값),
boolean flag // (정답 수열을 맨 상단 한개만 출력 조건),
pDFS() 메서드 // 수열 공식 핵심 로직,
bDFS() 메서드 // 문제 풀이 핵심 로직,
문제 핵심
첫째 파스칼의 수열 공식을 알고 있어야 한다.
공식 : n-1C0 ~ n-1 Cn-1
둘째 메모이제이션을 사용한 조합 로직을 구현할 수 있어야 한다.
셋째 순열 로직을 구현할 수 있어야 한다.
문제 풀이 과정
문제를 처음 접했을 때 파스칼의 수열 공식을 알고있지 못했다.
그래서 강의를 참고해서 공식을 배운 뒤에 문제를 풀이해 나갔다.
이틀에 걸쳐 문제를 풀었다.
계속 문제 풀이에만 몰두한 것은 아니고 하루 2시간씩만 할애했다.
자료구조를 생각해봤다.
파스칼의 수열 공식을 담아줄 배열 p와, 중복을 제외한 순열 값을 담아줄 배열 b가 필요했다.
일단 p배열에 파스칼 공식을 어떻게 담아줘야할지 고민해봤다.
파스칼의 공식은 조합을 사용하므로 pDFS를 n번 호출했어야 했다.
// pDFS n번 호출하기
for (int k = 0; k < n; k++) {
p[k] = T.pDFS(n - 1, k);
}
// PDFS 로직
public int pDFS(int n, int k) {
if (fibo[n][k] > 0) return fibo[n][k];
if (n == k || k == 0) return 1;
else return fibo[n][k] = pDFS(n - 1, k - 1) + pDFS(n - 1, k);
}n = 4이기 때문에 pDFS를 0 ~ 3까지 호출하게 되면 1 3 3 1이라는 값이 나오고 그 값을 차례대로 p 배열에 담아줬다.
b배열에는 핵심 로직이 들어간다.
첫째 중복을 제거한 순열의 경우의 수를 모두 구한다.
둘째 p배열과 b배열을 같은 인덱스끼리 곱해서 모두 더한 값을 sum에 담아주고 sum 값을 모두 출력해봤다.
셋째 sum 값에 16이 들어가는 것을 확인하고 sum == total일 때 b배열을 return 해주도록 했다.
넷째 여러개의 수열이 존재할 경우 맨 상단에 있는 수열만 출력하는 문제이므로 flag를 사용하여 이 조건을 충족시켰다.
핵심 코드
public void bDFS(int L) {
if (flag) return;
if (L == n) {
int sum = 0;
for (int i = 0; i < n; i++) {
sum += p[i] * b[i];
}
if (sum == total) {
for (int x : b) System.out.print(x + " ");
System.out.println();
flag = true;
}
} else {
for (int i = 1; i <= n; i++) {
if (ch[i] == 0) {
ch[i] = 1;
b[L] = i;
bDFS(L + 1);
ch[i] = 0;
}
}
}
}
개선된 점
첫째 문제에서 해결해야 하는 작은 부분부터 하나하나 해결해 나가서 결국 문제를 해결할 수 있게 되었다.
둘째 끝까지 포기하지 않고 문제를 풀었다.
피드백, 개선할 점
첫째 정답을 구하려고 마음이 급해지면 오히려 정답에서 멀어지게 되는 것 같다.
알고리즘은 처음 방향 선택이 중요하다.
방향을 잘못잡으면 아무리 오래 고민해도 답이 나올 수가 없다.
그래서 로직을 짤 때 논리적인 근거를 바탕으로 차근차근 짜야한다.
내가 무엇을 모르는지, 무엇을 아는지.
문제 해결 과정을 그려보면서 그 과정이 맞다면 어떻게 코드로 구현할지에 대해 생각해봐야 한다.
정답을 쫓을게 아니라 과정에 집중해야 한다.
느낀점
첫째 십리도 한걸음부터..
p배열을 만들고 b배열도 중복을 제거한 순열의 경우의 수를 구하는건 쉬웠기 때문에 그것부터 구하고,
그리고 그 순열의 경우의 수와 p배열을 곱해서 sum에다 넣어주는 로직을 구현하고
...
이런식으로 하나하나 해결해나가다 보니 어느샌가 문제를 해결했다.
크게 도약한 느낌이 들었던 풀이 과정이었다.
주먹구구식으로 코드를 짠 다음에 실행해서 정답이 아니면
또 다시 코드를 짜는 방식이 아니라.
알고리즘을 그려보고 논리적인 근거하에 하나하나 해결해 나간 풀이 과정이 스스로 뿌듯함을 느끼고, 인상적이었다.
오늘 풀이 과정을 잊지 말고 계속 가져갔으면 좋겠다.
둘째 나는 누군가와 대화하듯이 문제를 풀어나가거나, 문제에 스토리를 섞으면 더 잘 풀이되는 것 같다.
너무 무거운 느낌으로 접근하는게 아니라.
가볍고 상쾌하게 발걸음을 떼는 느낌?
누군가에게 설명하듯이 문제를 풀어나가면
더 논리적으로 문제를 해결하는데 큰 도움이 되는 것 같다.
일단 남에게 설명할 수 있다는 것은 그 지식을 활용할 수 있는 단계이기 때문이다.
만약 남에게 설명할 수 없다면 그 지식은 내것이 아니기 때문에
나는 모르는 상태라는걸 자각할 수 있고, 어느 부분을 개선해야하는지도 파악할 수 있다.
