백준 24267번- '알고리즘 수업 - 알고리즘의 수행 시간 6' (PYTHON 풀이)

문제:

해당 문제는 어제에 이어 시간복잡도와 관련된 문제이다. 이번엔 흔한 규칙이 아니라 직접 규칙을 찾아 수행 횟수를 출력해야했다.

몇십분간 이 문제를 붙잡으면서 규칙을 찾으려고 했는데, 너무 오래 걸려서 구글링의 도움을 받아 규칙을 찾아냈다. 참고한 글을 다음과 같다.

 

출처: https://velog.io/@jiiina/%EB%B0%B1%EC%A4%80-24267%EB%B2%88-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%88%98%ED%96%89-%EC%8B%9C%EA%B0%84-Java

[백준] 24267번 - 알고리즘 수행 시간 (Java)

 

규칙만 찾으면 코드 작성은 쉬울 거 같아 일부러 파이썬이 아닌 자바 글을 찾아보고, 코드는 보지 않았다.

해당 글에서 언급하다시피 풀이는 2가지가 존재하는데 단순히 눈치껏 푸는 방법과 조합 공식을 활용해서 푸는 방법이다.

눈치껏 푸는 방법은 3차항의 시간복잡도인 것을 확실하니 n(n-1)(n-2)로 잡고 예제 출력을 참고해서 6을 나눠 푸는 방법이다. 

 

해당 문제는 결과적으로

i는 1부터 (n-2)

j는 i+1부터 (n-1)

k는 j+1 부터 n까지 반복한다.

 

j는 i의 값을 참고하여 i보다 1만큼 큰 값부터 시작하고, k는 j보다 1만큼 큰 값부터 시작하기 때문에 i,j,k는 절대 중복될 수 없다는 규칙이 생기게 된다. 이를 통해 조합을 활용하면 된다는 것을 알 수 있다.

 

 

조합의 공식은 위와 같다. r은 선택하는 대상의 개수이므로 3을 대입하면 된다.

위 식을 정리하면 결과적으로 'n(n-1)(n-2)/6' 이 되기 때문에 이를 코드로 만들면 풀 수 있다.

 

풀이:

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

지난번처럼 '//'와 '/'의 차이를 주의하여 풀면 문제는 바로 풀린다!