예를들어 1 2 3 4 네개의 숫자가 나열되어있을때
파스칼삼각형처럼 합을 구해나가면 최종값이 구해진다
1부터 N까지의 숫자니까
경우의수는 N!이고
가장 윗줄에 있는 숫자를 다 더해가면서
답이 F가 나올때까지 하다가 F를 찾으면
stop하고 사전순으로 배열하면 되는데
이렇게하면 시간초과가 난다
규칙을 찾아보면
1 2 3이 있으면
첫번째 1+2, 2+3
두번째 1+2*2+3
(a+b)^2
1 2 3 4가 있으면
첫번째 1+2, 2+3, 3+4
두번째 1+2+2+3, 2+3+3+4
세번째 1+2*3+3*3+4
(a+b)^3
1 2 3 4 5가 있으면
첫번째 1+2, 2+3, 3+4, 4+5
두번째 1+2+2+3, 2+3+3+4, 3+4+4+5
세번째 1+2*3+3*3+4, 2+3*3+4*3+5
네번째 1*2*4+3*6+4*4+5
(a+b)^4
...
(a+b)^n처럼 이항계수 규칙을 가지고 있는데
(a+b)^n과는 다르게 N-1로 하면 규칙이 맞다
이 규칙을 코드로 표현하면
1부터 4까지 포문을 돌때
1(3C0), 3(3C1), 3(3C2), 1(3C3)가 되어야 하므로
이항계수 정보를 담을 n칸의 리스트를 1로 초기화하고
첫번째 항은 항상 1이니까 i가0일때는 1로 두고 3까지 돈다
첫번째 바퀴 i=1
b[1] = b[1-1]*(4-1)/1 == 3/1
두번째 바퀴 i=2
b[2] = b[2-1]*(4-2)/2 == 3*2/2*1 == 3
세번째 바퀴 i=3
b[3] = b[3-1]*(4-3)/3 == 3*2*1/3*2*1 ==1
분자 n-i 부분은 3, 2, 1 작아지며 곱하고
분모 i 부분은 1, 2, 3 커지면서 곱한다
이제 이미 쓰여진 숫자는 쓰지 않으니까
순열 구하기 문제처럼 중복된 가지는 없애고
부모노드로 돌아올때 체크를 초기화하면서
재귀함수로 모든 숫자를 순회하면 된다
꿈★은 이루어진다
내일채움공제 되는 중소기업 가자 화이팅!
해당 댓글은 삭제되었습니다.
아는형이 준 pdf로 풀고 있어요