- 백준 24267번 풀이2023년 07월 15일
- Lv. 34 라이츄
- 작성자
- 2023.07.15.:56
문제
https://www.acmicpc.net/problem/24267
이번에도 삼중 반복문인데... 아... 아무튼 실행 횟수랑 시간 출력하는거 맞음.
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만 남고 나머지는 나눠버릴 수 있다. 사실 저기서 삼중반복문? 이거 조합이네요? 하실 수도 있겠지만 아무튼.
'BOJ > [BOJ] Python' 카테고리의 다른 글
백준 19532번 풀이 (0) 2023.07.20 백준 24313번 풀이 (0) 2023.07.17 백준 24266번 풀이 (0) 2023.07.13 백준 24265번 풀이 (0) 2023.07.11 백준 24264번 풀이 (0) 2023.07.10 다음글이전글이전 글이 없습니다.댓글