https://www.acmicpc.net/problem/24267
문제
오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.
입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.
MenOfPassion 알고리즘은 다음과 같다.
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;
}접근 과정 / 풀이 과정
https://www.acmicpc.net/problem/24266
위 링크는 바로 전 문제이다. 전 문제와 달리 이번 문제는 조건식과 범위에 변화가 생겼다.
실행횟수가 N^3으로 간단 명료 했던 것과 다르다. 이번 문제는 고민을 많이 했던 것 같다.
암산으로는 실행 횟수를 가늠하기 어려워, 종이에 작성해가며 고민하였다.
입력값이 7이라고 가정해보자.
첫번째 for 문은 1 ~ 5까지이다.(n-2까지)
두번째 for문의 j는 반복상승한다.(n-1까지)
2 3 4 5 6 i가 1일 때 j
3 4 5 6 i가 2일 때 j
4 5 6 i가 3일 때 j
5 6 i가 4일 때 j
6 i가 5일 때 j
세번째 for문의 k이다.
i가 1일 때
3 4 5 6 7 j가 2일 때 k
4 5 6 7 j가 3일 때 k
5 6 7 j가 4일 때 k
6 7 j가 5일 때 k
7 j가 6일 때 k
i가 2일 때
4 5 6 7 j가 3일 때 k
5 6 7 j가 4일 때 k
6 7 j가 5일 때 k
7 j가 6일 때 k
i가 3일 때
5 6 7 j가 4일 때 k
6 7 j가 5일 때 k
7 j가 6일 때 k
i가 4일 때
6 7 j가 5일 때 k
7 j가 6일 때 k
i가 5일 때
7 j가 6일 때 k머리가 나쁘니 몸이 고생이다.
하지만 이렇게 모든 실행 과정을 작성하고나니 규칙이 보인다.
i가 1일 때 총 실행 횟수는 15회.
i가 2일 때 총 실행 횟수는 10회.
i가 3일 때 총 실행 횟수는 6회.
i가 4일 때 총 실행 횟수는 3회.
i가 5일 때 총 실행 횟수는 1회.
감소량이 처음 N-2에서 1씩 증가한다.
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
long N = Long.parseLong(bf.readLine());
long n = 0;
// i가 1일 때 총 실행 횟수는 15회
for(int i = 0; i < N-2; i++) {
n += N-2-i;
}
// 처음 15회에서 N-2-i씩 감소한 n을 sum에 더한다
long sum = n;
for(int i = 0; i < N-2; i++) {
n -= N-2-i;
sum += n;
}
System.out.println(sum);
System.out.println(3);
}
}
느낀점 / 배운점
처음 제출한 답안은 2중첩 for문을 사용하였는데, 이는 바로 시간초과로 오답처리 되었다.
그래서 공식 또는 규칙을 찾아 풀 수 밖에 없었다.
사람들이 입을 모아 말하길, 시간 복잡도는 개발하는데 있어서 매우 중요하다고 한다.
시간복잡도 카테고리에서 중요한 것을 배워 개발에 잘 적용하기를 바란다.
