[Java 자바] 백준 알고리즘 2775번 답 : 부녀회장이 될테야

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

2775번: 부녀회장이 될테야

 

 

<문제 해결 아이디어>

 

 

이렇게 직접 공책에 그려보다가 규칙을 찾았다,,,ㅋㅋ

---

아래 좀 더 예쁘게 나타내보면!

 

 

형광펜과 빨간 화살표의 관계를 보면 된다! 같은 색으로 색칠된 수들을 합해주면 빨간 화살표가 가리키는 숫자가 된다!

이게 가장 핵심 아이디어다!

그리고 층과 호수가 14까지로 제한되어있기 때문에 모든 호수 값을 미리 구해두면 된다.

이것도 두번째 핵심 아이디어인듯?! 왜냐면 딱 그 호수만 계산하려고 하면,, 복잡해서 머리 터지거든,,

그래서 DP문제인가? 했는데 위의 공식을 발견했고, 호수랑 층이 사이즈가 14로 작게 fixed 되어있는걸 발견했네,,ㅎㅎ

 

위의 그림에서 가장 왼쪽의 0은 사실 사용되지 않는 아파트 호 수이지만, 핵심 아이디어1 공식에 맞게 사용할 수 있다!

자바의 경우 배열을 생성하면 모두 0으로 초기화되는데,

그럼 각 층의 1호들도 [구하려는 집의 사람 수는 왼쪽 옆집과 아랫집의 수를 합치면 구할 수 있다]는 공식이 적용가능하다!

 

물론 아예 애초에 0층을 초기화해준 것처럼 모든 1호들도 1로 초기화해도 된닷!

근데 위의 아이디어를 떠올린게 뿌듯해서 고집부린거다 ㅋㅋ

 

<내 착각>

처음에 잘못 해석해서 아래 변수 제한 조건이 k랑 n이 1부터 14라는 조건인데, k는 1 이상인 정수, n은 14이하인 정수라고 해석했음,,,ㅋ

왜 k의 최대 범위를 안알려줬지하고.. 고민했네.. 그래서 그냥 일단 100이하라고 예상하고 풀었는데 다른 사람들 풀이보고 깨달음^^ㅋㅋ

 

 

<코드>

 

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        int human[][] = new int[15][15];

        for(int i=1;i<15;i++) //0층 셋팅
            human[0][i] = i;

        for(int i=1;i<15;i++){
            for(int j=1;j<15;j++){
                human[i][j] = human[i][j-1]+human[i-1][j];
            }
        }

        for(int i=0;i<T;i++) {
            int k = Integer.parseInt(br.readLine());
            int n = Integer.parseInt(br.readLine());

            sb.append(human[k][n]).append("\n");
        }
        System.out.println(sb);
    }
}

 

아 참고로 배열 15X15로 초기화한 이유는 1층 1호를 [1][1]로 딱 매칭시키고 싶어서~!