[Baekjoon] 2775 부녀회장이 될테야

[Bronze I] 부녀회장이 될테야 - 2775

문제 링크

성능 요약

메모리: 13092 KB, 시간: 132 ms

분류

구현(implementation), 수학(math)

문제 설명

평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.

이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다.

아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

입력

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

출력

각각의 Test case에 대해서 해당 집에 거주민 수를 출력하라.

---

알고리즘 과정

일단 이런 계산이 포함된 문제는 손으로 좀 경우의 수를 써봐야지 확실히 알고리즘을 찾을 수 있다.

나는 보여주기 위해 엑셀로 작성하여 보여주지만 이런 문제는 손으로 계산을 직접해보다 보면 발견하는 알고리즘이 꽤 있다. 되도록 손으로 한 번 문제를 풀고 시작하는 것이 좋다.

그림에서 보이는 연파랑색 부분은 이미 확정된 인원이다. 왜냐하면 문제에서 0층의 i호에는 i명이 산다고 했으니 맨 아래층이 완성되고 어쩌피 각 층의 1호들은 전 층의 1호의 합이므로 똑같이 1이다.

그리고 최대 층과 호수가 정해져 있으므로 배열을 미리 다 만들어두고 확정된 인원을 미리 설정해둔다.

위의 그림에서 보이는 빨간색 두개를 합하면 초록색의 답이 나온다.

그래서 초록색의 답이 나오려면 같은 층의 전 호수 + 전 층의 같은 호수를 더하면 된다.

이를 이용하면 미리 모든 호수를 설정해둘 수 있다.

그리고 내가 항상 까먹는 것은 배열의 크기를 설정하는 것인데 int[15]를 하면 0~14의 배열이 생성된다.

for(int i = 0; i < 15; i++){
            ap[i][1] = 1;
            ap[0][i] = i;
        }

위에 보듯이 이 문제 좀 더 편하게 풀려면 그냥 0호를 버리고 1호부터 1로 설정하면 편하다.

---

코드