백준 24267 - 파이썬

https://www.acmicpc.net/problem/24267

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

문제 풀이

이번 문제는 공식 유도하는게 힘들었다. 처음에는 노가다로 각 반복문마다 나오는 숫자들을 다 정리해 봤다. 그랬더니 1 + 3 + 6 + 10 + 15 = 35 라는 식이 나와서 이것을 코드로 만들어 봤다.

 

n = int(input())

sum = 1
tmp = 1
for i in range(2,n-1):
    tmp += i
    sum += tmp

print(sum)
print(3)

 

출력 결과가 35 일치해서 백준에 제출해 봤더니 틀렸다고 하였다. 고민하다가 구글링을 해봤다.

 

해당 블로그를 보고 공식을 유도할 수 있었고, 이해할 수 있었다. 여기서는 조합을 이용해서 공식을 유도했는데, 수학을 몇년 안했더니 전혀 떠올리지 못했다. 

 

i가 1일 때 j는 2가 되고, k는 3~7까지 나올 수 있다. 이를 쭉 나열해 보면 다음과 같다.

 

i = 1, j = 3, k = 4 ~ 7

i = 1, j = 4, k = 5 ~ 7

i = 1, j = 5, k = 6 ~ 7

i = 1, j = 6, k =  7

 

이처럼 중복 없이 123, 124, 125, 126, 127, 134 이렇게 숫자가 나오게 된다. 즉 nC3=n!/(n−3)!*3!가 된다.

따라서 수행 횟수는 n(n-1)(n-2)/6이 되고, 차수는 3이 된다.

 

n = int(input())

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

 

 

느낀점

오늘 문제를 풀면서 수학 공부 좀 다시 해야 되겠다고 느꼈다. 되게 기본적인 것인데 몇년 안하니까 떠올리기도 쉽지 않았던거 같다. 코딩 공부하는 것 외에도 수학도 복습해야 되겠다.