[자바] 백준 24265 - 알고리즘 수업 - 알고리즘의 수행 시간 4 (java)

 문제 : boj24265

---

 

필요 알고리즘 개념

• 수학, 구현
  
  • 모든 경우를 해보면 시간 초과가 날 것이므로, 간단한 수학지식이 필요한 구현 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  i는 [1, n-1], j는 [i+1, n] 이다. i가 n-1번 도는 동안 j는 순서대로 n-1, n-2, n-3, ... , 1번 돌게 된다. 따라서 n-1 + n-2 + ... + 1 이 답이 된다. 등차가 1인 등차수열의 합을 구하면 되므로 첫째 줄에는 n*(n-1)/2 를 출력해주면 된다.

 

  둘째 줄에는 수행 시간이 어떤 것에 비례하는지 적어주면 되는데, 문제에서 제시된 알고리즘은 n^2으로만 동작하므로 2를 고정적으로 출력해주면 된다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        System.out.println(1l*n*(n-1)/2);
        System.out.println(2);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}