24267:알고리즘의 수행 시간 6

풀이

n = int(input())
result = (n**3 - 3* n**2 + 2*n)//6
print(result,3,sep='\n')

1. i가 증가함에 따라 j와 k의 시작 지점이 하나씩 증가함 -> j와 k의 수행 횟수가 -1씩 증가함
2. i=1부터 n-2까지 증가함에 따라 k에서 코드 1의 수행 횟수는 $ \frac{(n-2)(n-1)}{2} $ ,..., $ \frac{(1)(2)}{2} $ 로 감소
3. 수행 횟수를 들여다 보면 일반항이 $ a_{n} $ = n(n+1)임을 알 수 있다
4. $ \sum_{n}^{i=1} = a_{n}$ 를 하면 답이 나온다

---

다른 사람의 풀이

n = int(input())
print(int(n*(n-1)*(n-2)/6))
print(3)

해당 풀이는 합이 아닌 경우의 수로 접근 한거다.

 

---

반복문은 '기계'다.

우리가 작성한 3중 반복문은 숫자를 하나씩 대입해보면서 조건(i < j < k)에 맞는 경우에만 "유효함!" 도장을 찍고 카운트를 올리는 기계라고 상상해 보자.

• 기계의 작동 방식:
  1. 숫자 1, 2, 3을 넣어봅니다. -> 조건 만족(1<2<3) -> "발권!" (1회 실행)
  2. 숫자 1, 2, 4를 넣어봅니다. -> 조건 만족(1<2<4) -> "발권!" (2회 실행)
  3. ...
  4. 숫자 3, 2, 1을 넣어봅니다. -> 조건 불만족(i<j<k 아님) -> "무시" (실행 안 함)

즉, 반복문의 수행횟수가 몇 회인지 알아낸다는건 기계가 정상 작동한 횟수를 센다는 것과 같다.

 

---

유효한 티켓의 규칙 = 조합

발권되는 티켓(실행되는 경우)에는 두 가지  특징이 있다.

1. 숫자가 3개 있어야 한다. (3중 반복문이니까)
2. 숫자가 모두 다르고 순서대로여야 한다. (조건 i < j < k)

,즉 "n 개의 숫자 중에서 서로 다른 3개를 그냥 뽑기만 하면" 이 티켓은 무조건 발권!!

• 예시 (n=5):
  • 당신이 주머니에서 숫자 5, 1, 3을 뽑았습니다.
  • 이 숫자로 만들 수 있는 유효한 티켓은 무엇일까요?
  • (5, 1, 3) -> 무시! (순서 안 맞음)
  • (1, 5, 3) -> 무시! (순서 안 맞음)
  • 오직 (1, 3, 5) 하나뿐입니다. (i=1, j=3, k=5)

정답 $$ _nC_3 = \frac{n \times (n-1) \times (n-2)}{3 \times 2 \times 1} = \frac{n(n-1)(n-2)}{6} $$