[JAVA] 2775번 - 부녀회장이 될테야

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

K층 N호에 몇명이 사는지 구해야한다.

 

• 0층에서:
  • 1호에는 1명
  • 2호에는 2명
  • 3호에는 3명
• 1층에서:
  • 1호: 0층 1호에 사는 사람 수 → 1명
  • 2호: 0층 1호 + 2호에 사는 사람 수 → 1 + 2 = 3명
  • 3호: 0층 1호 + 2호 + 3호에 사는 사람 수 → 1 + 2 + 3 = 6명
• 2층에서:
  • 1호: 1층 1호에 사는 사람 수 → 1명
  • 2호: 1층 1호 + 2호에 사는 사람 수 → 1 + 3 = 4명
  • 3호: 1층 1호 + 2호 + 3호에 사는 사람 수 → 1 + 3 + 6 = 10명

 

그래서 문제에 있는 2층 3호에 사는 사람의 수는 10명이다.

딱봐도 생긴게 피보나치문제와 비슷하게 풀어야할것 처럼 생겼다

 

일반화를 해보자면

특정 층의 N호에 사는 사람 수 = 그 아래층 1호~ N호까지 모든 사람 수의 합 이다

예를들어 4층 4호에 사는 사람 수를 구하려면 3층 1호부터 4호까지 사람 수를 더하면 되는데

3층 각 호에 사는 사람의 수는 2층을 알아야하고, 결국 0층까지 필요하다.

 

뭔가 직감적으로 몇 번 계산하면 규칙이 있을 것 같아서 적어봤다

이렇게 적어보고

표를 만들어보면 규칙이보인다 예를들어

2층 5호 =2층 4호 + 1층 5호

일반화하면

arr[i][j] = arr[i][j-1] + arr[i-1][j] 이다 

 

층과, 호수가 필요하니까 이차원 배열을  쓰고,

문제에서 알 수 있는 부분은 미리 계산하여 배열에 값을 넣어준다!! (어제 배운 메모이제이션)

미리 구할 수 있는 점

[i][1] = 1 

-> 모든 층의 1호에는 1명이 산다

[0][i] = i

 -> 0층의 각 호수에는 호수 번호랑 똑같이 일치하는 사람 수가 산다

 

 

 

시간복잡도

이중반복문으로 배열을 채울건데 k,n의 값 자체가 작아서 딱히 문제는 없다

O(196)이 걸린다 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

 

1.t,k,n을 입력받는다

2.이차원배열을 만들고, 채울 수 있는 값은 미리 채운다

3. 남은 층수도 채운다

4. 출력

 

 

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
             
        int t = Integer.parseInt(br.readLine());  
        StringBuilder sb = new StringBuilder();
    	int arr[][] = new int[15][15];
    	
    	for(int i=0; i<15; i++) {
    		arr[i][1] = 1; //모든 층의 1호는 1명이 산다
    		arr[0][i] = i; //0층은 호수만큼 사람이 산다 
    	}
    	
    	//구현//
    	for(int i=1; i<15; i++) {
    		for(int j=1; j<15; j++) {
    			arr[i][j] = arr[i][j-1] + arr[i-1][j];
    		}
    	}
    	
    	for(int i=0; i<t; i++) {	
    		int k = Integer.parseInt(br.readLine());
        	int n = Integer.parseInt(br.readLine());
        	sb.append(arr[k][n] + "\n");
    	}
        System.out.println(sb);
	}
}