[백준/자바/JAVA] 3004 : 체스판 조각

---

[문제]

상근이는 3003번에서 동혁이가 발견한 체스판을 톱으로 자르려고 한다.

상근이는 체스판을 최대 N번 자를 수 있으며, 변에 평행하게만 자를 수 있다. 또, 자를 때는 체스판의 그 변의 한쪽 끝에서 다른쪽 끝까지 잘라야 한다. 자른 후에는 조각을 이동할 수 없다.

이때, 최대 몇 조각을 낼 수 있는지 구하는 프로그램을 작성하시오.

{ 입 출력 예제 }

---

[문제풀이]

다른 방법도 많겠지만 이 문제를 보고 바로 떠오른 방법으로 풀이해보았다. 내 풀이는 자르는 횟수를 홀수의 경우와 짝수의 경우로 나누어 풀이 하는 것이다.

---

짝수의 경우

자르는 횟수가 $n$ 일 때, 최대 조각은 $x_{n}$ 이다.

$n$ 이 짝 수라면

$x_{2}= 2 \times 2$, $x_{4}= 3 \times 3$, $x_{6}= 4 \times 4$, $x_{8}= 5 \times 5\dotsb$

와 같은 패턴을 보입니다.

패턴을 좀더 편하게 보기 위해 $n$을 2로 나누면
아래와 같은 식을 보입니다.

$x_{1}= 2 \times 2$, $x_{2}= 3 \times 3$, $x_{3}= 4 \times 4$, $x_{4}= 5 \times 5\dotsb$

즉, 짝 수의 경우 일때 최대 조각을 구하는 식은

$x_{n}=\{(n\div2)+1\}^{2}$

이 성립됩니다.

---

홀수의 경우

이 경우는 가로, 세로 선의 개수에서 행, 열 칸의 개수 구하는 식으로 풀었습니다.

왜? 그냥 떠오른 식이라서

자르는 횟수가 $n$ 일 때, 최대 조각은 $x_{n}$ 이다.

행, 열 칸의 개수를 구하기 전에 가로, 세로 선의 개수를 먼저 파악 합니다.

선의 개수 ( 가로 $\times$ 세로 )

$x_{1}=0\times1$, $x_{3}=1\times2$, $x_{5}=2\times3$, $x_{7}=3\times4\dotsb$

위의 대입 예시를 토대로 아래와 같은 식을 생각할 수 있습니다.

$x_{n}$ 을 자른 가로$\times$세로 개 수 구하는 식

$\left\lceil\cfrac{(n-1)\times(n+1)}{2}\right\rceil$

그리고 행$\times$열 칸의 개수를 살표 보면 다음과 같습니다.

$n$ 이 홀 수일 때, 칸의 개수 ( 행 $\times$ 열 )

$x_{1}= 1 \times 2$, $x_{3}= 2 \times 3$, $x_{5}= 3 \times 4$, $x_{7}= 4 \times 5\dotsb$

즉, 자른 횟수 ( 가로 $\times$ 세로 ) 보다
칸의 개수 ( 행 $\times$ 열 ) 가 한개씩 많은 것을 확인 가능합니다.

행 = $\cfrac{(n-1)}{2}+1$

열 = $\cfrac{(n+1)}{2}+1$

---

[코드작성]

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

public class Main {
	private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
	public static void main(String args[]) throws IOException{ 
		int A = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		bw.write(sb.append(printNum(A)).toString());
		bw.close();
	}
	

	static int printNum(int num) {
		if(num%2!=1) { 		// 짝수의 경우
			num = num/2;
			num = num+1;
			num*=num;
			return num;
			
		}else { 			// 홀수의 경우
			
			int row = ((num-1)/2)+1;
			int col = ((num+1)/2)+1;
			
			return row*col;
		}
	}
}