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

문제

시간복잡도 개념 보러가기

 

 

풀이

풀이에는 두 가지 방법이 있다.

1. 시그마로 계산하는 방법

2. 경우의 수 구하기

 

수학 안본지 6년이 넘어서 .. 공식을 찾는게 너무 어려워 다른 분 블로그를 참고했다. 정리하자면, 아래 경우의 수의 규칙이 아래와 같다. 

(1,2,3) ... (1,6,7)

(2,3,4) ... (2,6,7)

 

때문에 아래와 같이 나올 수 있게 된다.

 

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

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

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

i = 4/ j 5/ 6, 7
       j 6/ 7

i = 5/ j 6/ 7

 

 

개인적으로 이해하기 쉽게 제일 잘 정리되어있던 분 !!

https://yester-today.tistory.com/7

백준 24267번 풀이 (Java)

 

 

 

 

코드

package AlgorithmStudy.src.bronze;

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

public class B24267 {
    public static void main(String[] args) throws IOException {
        /*
        n = 7
        i = 1/ j 2/ 3, 4, 5, 6, 7   /5
               j 3/ 4, 5, 6, 7  /4
               j 4/ 5, 6, 7     /3
               j 5/ 6, 7        /2
               j 6/ 7           /1

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

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

        i = 4/ j 5/ 6, 7
               j 6/ 7

        i = 5/ j 6/ 7
         */
        // n* (n-1) * (n-2) /6

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BigInteger n = BigInteger.valueOf(Integer.parseInt(br.readLine()));

        System.out.println(n.multiply(n.subtract(BigInteger.valueOf(1))).multiply(n.subtract(BigInteger.valueOf(2))).divide(BigInteger.valueOf(6)));
        System.out.println(3);

    }
}

 

 

 

하 ... 수학 진짜 다 까먹었다 ...