순열 조합같은거 재귀로 푸는 방법밖에 없냐?

[익명(112.155)]

순열조합 문제 풀다가 어케 푸는 지 모르겠어서 구글링 해보니까 죄다 재귀로 푸는거 같노.

[c언어입학(112.153)]

반복문 이용해도 짤 수는 있음.. 단지 하드코딩이라 꺼려하는 것 뿐

[c언어입학(112.153)]

단순하게 이항정리를 이용한 방식이 젤 빠름

[c언어입학(112.153)]

https://mlogic.tistory.com/entry/nCrn-1Cr-1-n-1Cr

[익명(112.155)]

종이에다 수식적어서 풀땐 쉬워보이는데 코드로 짤려고 하면 존나 어려움. 내가 빡대갈인듯.

[c언어입학(112.153)]

쉽게 생각해서 queue나 vector로 index값을 (n,r)2개로 한다음에 첫번째 n 루프 돌고 두번 째 루프에서 queue의 top()이 n이거나 vector의 index값중 n이 같은 게 있으면 n이 아니게 될 때 까지 루프 돌려 그 다음 n==1 r==1 중 하나면 sum에 다 더해버리기. + 만약 n-r==1 이어도 더하는거 이용하면 최적화 될듯

[c언어입학(112.153)]

두 개 받는 방법은 pair를 쓰던가.. map을 쓰던가.. 구조체로 2개 받아서 하든가.. 등 등

[c언어입학(112.153)]

queue top이 아니라 front임

[c언어입학(112.153)]

그냥 멍청한 방법이긴 한데 일케 해도 하나의 방법임 5c4=(5c1이긴 한데 일단 그건 넘어가고)= (1*2*3*4*5)/(1*2*3*4) 일케 하는 것도 방법이긴함

[c언어입학(112.153)]

1시간 후에 고민 해도 안되면 답글 다셈.. 오늘 어제 놀아서 이제 코드 짜야되서 바쁠거같음

[c언어입학(112.153)]

근데 생각해보면 얘도 O(max(n,r)) 아닌가 r>n경우 예외만 잡아주면 잘 돌아갈 것 같은데 n이 100이고, r이 30이면 1부터 100까지 게속 곱하기 한다음n에 넣고(n=1로 선언) r이 1부터 30까지 계속 곱하기 한다음에 r넣고.. 그러나, int값이 더할 때보다 훨씬 범위가 증가하는게 단점이네.. 근데 지금 갑자기 생각났는데 r부터 n까지 돌려도되는거 아냐?

[c언어입학(112.153)]

7c3이면 (1*2*3*4*5*6*7)/(1*2*3) 인데, 어차피 나누면 4*5*6*7 아니냐? 이거 해볼만 하다

[익명(112.155)]

일단 (1*2*3*4*5)/(1*2*3*4)와 같은 방식 해본적 있는데, 오버플로우 나온적 많아서 안 좋은 방법인듯. 일단 답변 ㄳ

[c언어입학(112.153)]

그러면 그냥 5c4니까 5 한번만 돌게 하면 끝 아냐?

[익명(112.155)]

ㅇㅇ 내가 근데 읽다보니 처음에 질문을 잘못한듯 ㅇㅇ