[Java] 백준 24263 알고리즘의 수행 시간 4 풀이 / 시간 복잡도

문제

시간복잡도 개념 보러가기

 

 

 

풀이

n == 7
i = 1/ 2, 3, 4, 5, 6, 7,/ 6
i = 2/ 3, 4, 5, 6, 7/ 5
i = 3/ 4, 5, 6, 7/ 4
i = 4/ 5, 6, 7/ 3
i = 5/ 6, 7/ 2
i = 6/ 7/ 1

2	3	4	5	6	7
3	4	5	6	7	0
4	5	6	7	0	0
5	6	7	0	0	0
6	7	0	0	0	0
7	0	0	0	0	0
0	0	0	0	0	0

 

6 + 5 + 4 + 3 + 2 + 1 로 결과가 나오는 것을 알 수 있다. 이는 위 표를 보면, 6 * 7의 절반인 것을 알 수 있다. 공식은 n(n-1)/2 이다.

 

 

코드

package AlgorithmStudy.src.bronze;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class B24265 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BigInteger n = BigInteger.valueOf(Integer.parseInt(br.readLine()));

        BigInteger a = n.subtract(BigInteger.valueOf(1));

        // n-1) *
        System.out.println(n.multiply(a).divide(BigInteger.valueOf(2)));
        System.out.println(2);



        /*
        n == 7
        i = 1/ 2, 3, 4, 5, 6, 7,/ 6
        i = 2/ 3, 4, 5, 6, 7/ 5
        i = 3/ 4, 5, 6, 7/ 4
        i = 4/ 5, 6, 7/ 3
        i = 5/ 6, 7/ 2
        i = 6/ 7/ 1
         */
    }
}