문제
이번에도 삼중 반복문인데… 아… 아무튼 실행 횟수랑 시간 출력하는거 맞음.
Reference
풀이
이 문제를 본 본인 표정:
근데 솔직히 이럴만 했다.
MenOfPassion(A[], n) {
sum <- 0;
for i <- 1 to n - 2
for j <- i + 1 to n - 1
for k <- j + 1 to n
sum <- sum + A[i] × A[j] × A[k]; # 코드1
return sum;
}아무튼 3중 반복문인 건 알겠는데 이게 뭔 패턴인가… 파이썬으로 해보자.
import sys
k = int(sys.stdin.readline())
sum = 0
for x in range(1, k-1):
for y in range(x+1,k):
for z in range(y+1,k+1):
sum += 1
print(sum)봐도 모르겠다면 정상이다. 나도 그래요… 일단 저게 뭐냐… 5를 입력하면 x는 1부터 5-1(4)까지니까 1, 2, 3이 된다. 파이썬 range는 ~이상 ~미만이잖음. 그리고 y는 1+1(2)부터 5까지니까 2, 3, 4가 된다. z는 2+1(3)부터 5+1까지니가 3, 4, 5다. 이걸 1 2 3, 1 2 4 이런 식으로 조합한다음 가짓수를 보는건데… 왜 35인지 당최 모르겠는겨.
그럼 저 옮긴거 내면 어떻게 되냐… 시간초과 뜹니다.
찾아보니까 시그마 전개로 푼 사람도 있었는데 솔직히 봐도 모르겠음… 그러던 와중에 참고문헌을 발견했는데…! 이게 글쎄….! nC3의 형태였던것이다! 그니까 조합이라고! 그럼 진짜 그런지 한번 해보자. 7을 넣었을 때 35가 나왔다고 했는데…
저 표기 nC3이랑 같은겁니다. 아무튼 조합 구하는 공식은 nCr = n!/r!(n-r)!이니까 저거 맞다.
팩토리얼 아시죠? 팩토리얼을 다 풀어보면 7! 안에는 4!도 3!도 있다. 나눠줍시다.
사실 내가 안에 4!도 3!도 있다고 했던 건 4*3*2*1 얘기한거였는데 보니까 4! 4! 나누고 나서도 3!이 있죠? 저기 6 있잖아.
import sys
k = int(sys.stdin.readline())
print((k * (k-1) * (k-2)) // 6)
print(3)그럼 분모에 왜 6이 오는지는 아실텐데 왜 n * n-1 * n-2가 오는지는 이해가 안가시죠들? 위에 팩토리얼 푼 걸 보면 아시겠지만 nC3이기때문에 공식이 n!/3!(n-3)!이 되는데, 이렇게 되면 n!에서 n * n-1 * n-2만 남고 나머지는 나눠버릴 수 있다. 사실 저기서 삼중반복문? 이거 조합이네요? 하실 수도 있겠지만 아무튼.
Reply