[백준] 15236번 : Dominos - JAVA [자바]

www.acmicpc.net/problem/15236

15236번: Dominos

 

---

• 문제

 

 

 

 

오늘은 조금 특별하게 영어 문제를 들고 왔다. 어렵지 않은 문제라 쉽게 풀 수 있다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

 

해석하기 귀찮으신 분들을 위해 간략히 문제를 설명드리자면 이렇다.

 

1. 입력받는 N 은 '한 블럭'에 찍힐 수 있는 점의 최대 개수다. (도미노 한 개는 두 블럭으로 이루어져 있다.)

2. 윗 블럭은 아래 블럭보다 점이 많을 수 없다.

3. 그림의 규칙을 보고 점이 0개 일 때부터 도미노의 두 블럭에 N개의 점이 모두 찰 때까지 나열했을 때 찍히는 점의 모든 개수를 출력하면 된다.

 

그림으로 보자면 이렇다.

 

N = 0 

출력 : 0

 

 

 

 

N = 1

출력 : 3 

 

 

 

N = 2

출력 : 12

 

 

 

N = 3

출력 : 30

 

 

 

 

이렇게 점의 개수를 출력하는 문제다.

물론 반복문으로 풀 수도 있지만, 수학적으로 접근해보도록 하자.

 

일단 윗 타일과 아랫 타일로 나눠서 생각해볼 필요가 있다.

 

 

1. 윗 타일 부터 생각해보자.

 

N = 1 일 때는 0 ~ 1 

N = 2 일 때는 0 ~ 2

N = 3 일 때는 0 ~ 3

      ⋮

N = n - 1 일 때는 0 ~ (n - 1) 

N = n 일 때는 0 ~ n 개가 찍힐 것이다. 

 

이 것을 모두 합해보자면 이렇다.

N = n 일 때, 1은 n 번 반복되고, 2 은 n-1 번 반복되고, 3 는 n-2 번 반복되고, ⋯ n-1 은 2 번 반복되고, n 는 1 번 반복된다.

 

그럼 임의의 k 에 대해서는 n - k + 1 번이 반복된다는 것을 알 수 있다.

그리고 (n - k + 1)이 총 k 번 반복되므로 0~k 까지 윗 타일의 점의 총 개수는 k(n - k + 1) 가 된다.

 

 

아래 타일을 보자.

N = 1 일 때는 1이 2번,

N = 2 일 때는 2가 3번

N = 3 일 때는 3이 4번

      ⋮

N = n - 1 일 때는 (n - 1) 이 n번 

N = n 일 때는 n 가 n + 1 번 찍힐 것이다.

 

0~k 까지의 아래 타일의 합은 k(k + 1) 이 된다.

 

 

 

이제 윗 타일과 아래 타일의 두 식을 합치면 이렇다.

 

k(n - k + 1) + k(k + 1)

= kn - k2 + k + k2 + k

= k(n + 2)

 

그럼 k에 대해 = 0~n이라고 하면 다음과 같이 수식이 완성된다.

 

 

 

이 공식을 그대로 쓰면 된다.

 

또한 n(n + 1)(n + 2) 는 항상 짝수이므로 정수로 나눠도 무방하다.

 

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

Scanner와 BufferedReader 입력방식을 각각 나눠서 비교해보겠다.

 

1 . Scanner 

2. BufferedReader

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner]

 

import java.util.Scanner;

public class Dominos {
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		
		System.out.println((N * (N + 1) * (N + 2)) / 2);
	}
}

 

 

 

 

 

---

- 방법 2 : [BufferedReader]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다.

 

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

채점 번호 : 23609680  -  방법 2 : BufferedReader

채점 번호 : 23609674  -  방법 1 : Scanner

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

---

• 정리

 

이번에는 조금 간단하면서 쉬운 문제를 풀이해봤다. 아무래도 여러 알고리즘 문제를 풀이하는데 위 문제처럼 공식을 찾아내는 연습을 하면 도움이 많이 되기 때문에 이러한 부류의 문제들을 많이 익혀보면서 영어 독해 능력도 키워보면 어떨까 싶다.