[백준] 2775번 : 부녀회장이 될테야 - JAVA [자바]

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

2775번: 부녀회장이 될테야

---

• 문제

 

 

어렵지 않은 문제다!

 

※주의할 점

1. 가장 첫 줄에 테스트 케이스가 주어진다
2. 테스트 케이스(첫 줄) 다음부터 두 줄씩 묶어 k 와 n 이 주어진다.
3. 아파트에는 0층부터 있고, 각 층에는 1호부터 시작한다.

---

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

 

Scanner 로 입력받아 연산하는 방법과 BufferedReader 로 입력받아 연산하는 방법, 두 가지 방법을 통해 풀이해보고자 한다.

 

---

• 알고리즘

 

문제에서 보면 a 층 b 호에 살기 위해서는 (a-1) 층의 1 호부터 b 호까지 사람들 수의 합만큼 사람들을 데려와 살아야한다고 쓰여있다.

입력받는 변수인 k 와 n 으로 표현하자면 다음과 같다.

 

k 층 n 호 = ( k - 1 ) 층 1 호 + ( k - 1 ) 층 2 호 + ⋯ + ( k - 1 ) 층 n 호

 

 

 

일단 예시로 필자가 표를 보여주겠다.

 

 

 

위 표를 보면서 이해해보자.

 

만약 k = 5, n = 8 이 주어졌다고 생각해보자.

그러면 4층의 1 호부터 8호까지의 합, 즉 아래의 표처럼 빨간색 박스의 합이 파란색 박스의 값이 되는 것이다.

 

 

 

 

그럼 알고리즘을 어떻게 짤 수 있을까?

먼저 2차원 배열을 쓰면 해결할 수 있을 것 같다.

 

입력에서는 다음과 같이 말하고 있다.

 

"첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다. (1 <= k <= 14, 1 <= n <= 14)"

 

즉, 테스트 케이스 수만큼 반복적으로 배열을 생성해주기 보다는 입력의 최댓값만큼의 배열의 사이즈를 한 번 생성하고 사용하면 더 효율적일 듯 하다.

 

int[][] APT = new int[15][15];

0~14 의 범위를 갖고 있기 때문에 15, 15 사이즈의 2차원 배열을 선언한다. ( 위 표랑 같게 만든다. )

 

그리고 배열에서 0 층은 1, 2, 3, 4, 5, ⋯ 로 초기화 해주고, 1 호는 모두 1 로 초기화 해준다.

( 앞의 인덱스는 층, 뒷 인덱스는 호로 본다.)

 

int[][] APT = new int[15][15];

for(int i = 0; i < 15; i++) {
	APT[i][1] = 1;	// i층 1호
	APT[0][i] = i;	// 0층 i호
}

 

그림으로 보자면 위 코드가 채운 곳은 아래와 같다.

 

 

 

 

 

 

그리고 다음으로 나머지 빈 자리를 채워줘야 한다.

 

1 층의 2호부터 14 층의 14호까지 반복해야한다. 그러면 어떻게 짤 수 있을까?

일단 이중 for 문이 필요하겠다.

 

int[][] APT = new int[15][15];

for(int i = 0; i < 15; i++) {
	APT[i][1] = 1;	// i층 1호
	APT[0][i] = i;	// 0층 i호
}


for(int i = 1; i < 15; i ++) {	// 1층부터 14층까지

	for(int j = 2; j < 15; j++) {	// 2호부터 14호까지

	}
}

 

 

 

그리고 덧셈을 어떻게 해야하는지는 아래를 보면 알 수 있다.

 

즉, i 층의 직전 호(j-1) 와 j 호의 아래층(i-1) 의 합을 채우면 된다. 즉 코드로는 아래와 같다.

 

 

int[][] APT = new int[15][15];

for(int i = 0; i < 15; i++) {
	APT[i][1] = 1;	// i층 1호
	APT[0][i] = i;	// 0층 i호
}


for(int i = 1; i < 15; i ++) {	// 1층부터 14층까지

	for(int j = 2; j < 15; j++) {	// 2호부터 14호까지
		APT[i][j] = APT[i][j - 1] + APT[i - 1][j];
	}
}

 

이런식으로 구조를 짜면 된다.

 

 

 

그리고 k 과 n 를 입력받을 때마다 APT 배열의 원소, APT[n][k] 를 출력해주면 된다.

---

• 풀이

- 방법 1 

 

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		
		// 아파트 생성 
		int[][] APT = new int[15][15];

		for(int i = 0; i < 15; i++) {
			APT[i][1] = 1;	// i층 1호
			APT[0][i] = i;	// 0층 i호
		}


		for(int i = 1; i < 15; i ++) {	// 1층부터 14층까지

			for(int j = 2; j < 15; j++) {	// 2호부터 14호까지
				APT[i][j] = APT[i][j - 1] + APT[i - 1][j];
			}
		}
		
		// 테스트 부분 		
		int T = in.nextInt();
		
		for(int i = 0; i < T; i++) {
			int k = in.nextInt();
			int n = in.nextInt();
			System.out.println(APT[k][n]);
		}
	}

}

 

 

가장 기본적인 방법이다.

 

생각보다 쉽지 않은가?

---

- 방법 2 

 

 

BufferedReader 을 쓰는 방식이다.

 

그리고 반드시 자료형 타입을 잘 보아야 한다.

br.readLine() 은 문자열로 데이터를 읽으니 반드시 꺼내서 쓸 때 int 형으로 쓰고자 한다면 Integer.parseInt()로 String 을 int 형으로 변환시켜준다.

 

그리고 코드가 보기 불편하니까 배열을 생성하는 메소드로 따로 묶어서 써보고자 한다.

 

출력또한 결과를 모아두었다가 한 번에 출력하도록 하기 위해 StringBuilder 을 추가해볼 것이다.

 

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

public class Main {

	public static int[][] APT = new int[15][15];

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		make_APT();	// 아파트 만들기 
		
		int T = Integer.parseInt(br.readLine());

		for (int i = 0; i < T; i++) {
			int k = Integer.parseInt(br.readLine());
			int n = Integer.parseInt(br.readLine());
			sb.append(APT[k][n]).append('\n');
		}
		System.out.println(sb);
	}

	
	public static void make_APT() {
		// 아파트 생성

		for (int i = 0; i < 15; i++) {
			APT[i][1] = 1; // i층 1호
			APT[0][i] = i; // 0층 i호
		}

		for (int i = 1; i < 15; i++) { // 1층부터 14층까지

			for (int j = 2; j < 15; j++) { // 2호부터 14호까지
				APT[i][j] = APT[i][j - 1] + APT[i - 1][j];
			}
		}
	}

}

 

 

 

위 코드를 실행하면 Scanner 보다 BufferedReader 가 속도가 빠르니 시간이 단축될 것이다.

---

• 성능 차이
  

 

 

위에서 부터 순서대로

 

채점 번호 : 18931988  -  BufferedReader

채점 번호 : 18931982  -  Scanner

 

시간을 보면 BufferedReader 와 Scanner 의 성능차이를 볼 수 있다.

 

그리고 BufferedReader 로 푼 것은 StringBuilder 을 사용했는데, 사용하고 안하고의 차이 또한 시간차이가 조금 난다. 한 번 기회가 된다면 테스트 해보시길 바란다.

---

• 정리

이번 문제 또한 어렵지 않게 풀 수 있다.

 

(만약 어렵다면 필자가 글 쓰는 능력이 떨어져서일 것...)

이해가 안된다면 꼭 댓글 남겨주시기 바란다. 필자도 피드백 받으면서 더 좋은 글을 쓸 수 있도록..