[백준] java 15439 베라의 패션

https://www.acmicpc.net/problem/15439

문제

베라는 상의 N 벌과 하의 N 벌이 있다. i 번째 상의와 i 번째 하의는 모두 색상 i를 가진다. N 개의 색상은 모두 서로 다르다.

상의와 하의가 서로 다른 색상인 조합은 총 몇 가지일까?

입력

입력은 아래와 같이 주어진다.

N

1 ≤ N ≤ 2017
N은 정수이다.

풀이과정

쉬운 문제인 것 같다. 간단하게 이중 반목문으로 상의 N벌과 하의 N벌을 돌려 같은 숫자가 아닐 때만 색상 카운트를 더하면 될 것 같다. O(N²)이지만 N의 최대 범위가 2017이므로 시간제한에도 걸리지 않을 것 같다.

효율성을 더 줄이는 방법을 찾아보자. 베라는 상의 N벌과 하의 N벌이 있다고 했다. 즉, 상의와 하의의 개수가 항상 똑같다. N이 5라고 가정해보자. 그리고 색상을 숫자로 바꿔보겠다.

i번 째 상의 하의는 항상 같은 색이므로 같은 색(이미지에선 같은 숫자)은 색상 카운트에 포함시키지 않는다. 1은 (2, 3, 4, 5)와 짝이 이루어지므로 첫 번째 색상의 색상 카운트는 4이다. 2는 (1, 3, 4, 5)와 짝이 이루어지므로 두 번째 색상의 색상 카운트 또한 4이다. 모든 숫자에 대해 짝을 지어보니, 모든 숫자에 대한 색상 카운트는 4인 것을 알 수 있었다.

따라서 해당 문제의 모든 예제에 대한 패턴은 N * (N - 1)이다.

이 패턴을 이용하여 효율성을 O(N²)에서 O(1)까지 줄일 수 있었다.

다음은 java로 제출한 풀이 코드이다.

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