백준 2775번
https://www.acmicpc.net/problem/2775

---

문제

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

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

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

---

입력

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

---

생각하기

동작
몇층 몇호에 몇명이 사는지 알고싶다면 그냥 0층 부터 찾고자하는 층까지 순서대로 올라가면서 계산하면 된다

층과 호수를 반복해야 하기 때문에 2중 for문을 사용한다.
그리고 각 층의 1호는 공통적으로 모두 1명이기 때문에 n이 1일 경우 굳이 반복하지 않고 바로 1을 출력할 수 있게 if문으로 해주고

else 부분이 n이 1이 아닐경우 즉, 1호가 아닌 경우에만 계산할 수 있도록 구현했다.

LinkedList 사용이유
자료구조는 LinkedList 를 사용했다.
처음에 List 를 사용했었는데, 층수가 올라가다보니 막히는 부분이 있었다.

예를 들어 2층 3호를 구하려고 할때, 처음 0층 1호부터 3호까지의 인원수를 list에 집어 넣으면 [1,2,3]의 값이 list에 들어가게 된다.

그 다음 1층의 인원수 부터는 아랫층의 인원수의 영향을 받기 때문에 이전 층수의 호수 데이터가 있어야 한다. 층의 호수를 반복하는 j 반복문은 계속해서 1호부터 반복하기 때문에 list.get() 을 통해 값을 꺼낼때 첫번째부터 꺼내지게 된다. 우리가 list를 통해서 주민들의 값을 계속 더해서 넣으면 list의 뒤로 값이 들어가게 되기 때문에 정확한 값을 출력할 수 없게 된다.

해당 부분을 고민하다가 head 와 tail 모두 활용할 수 있는 LinkedList가 가장 적합하겠다는 생각을 하게되었다.

각 호의 거주민 숫자는 linkedList.add()를 통해서 집어 넣고,
다음 층을 넘어갔을 때는 다시 linkedList.poll()을 통해 앞에서 부터 값을 꺼내서 sum += 을 통해서 계속 더해 나간다.

그리고 각 층의 호수를 모두 반복하고 난 후 다시 sum을 0처리 해줘야 한다.
이유는 각 층의 1호는 모두 1명이기 때문에 계속 누적된 합을 적용하면 제대로 된 값이 나오지 않는다.

해당 방식을 각 층의 숫자 만큼 반복하고, 마지막에 linkedList.getLast()를 통해 linkedList의 마지막에 있는 거주민 수를 구할 수 있다.

거주민 수 계산을 마친후에는 linkedList.clear()를 꼭 해줘야 한다.
그래야 다음 결과 값을 또 구할 수 있으니까.

TMI

처음에 규칙을 찾으면 풀수 있는 문제라고 생각이 들었다.
그래서 규칙을 찾으려고 진짜 별 x랄을 다했는데 찾지 못함

친구의 도움을 통해 등차수열이라는 걸 알게되면서
그냥 쓸데없는 짓 하지말고 아래부터 계산해서 올라오는게 맞구나 생각하게 됬다..

근데 여기서 문제

규칙찾기가 어려운게 문제가 아니었음
하다보니 0층부터 시작해서 계산하는 것도 for문에서 버벅이고 있는 내 모습을 발견함..
이전 층의 거주민 수를 어떻게 가져와야 되는지 반복문에서 엄청 고민함

어찌됬든 문제를 풀었지만 풀고나서 느낀점

진짜 아랫집 사람을 왜 데리고 살아야 하며,
내가 그 숫자를 왜 알아야 하냐고.. 이딴 아파트 만든 놈 누구냐?

걍 다 꺼져

---

코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());
		LinkedList<Integer> linkedList = new LinkedList<>();		

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

			if(n==1) {
				linkedList.add(1);
			}
			else {
				int sum = 0;
				for(int l=0; l<=k; l++) {

					for(int j=1; j<=n; j++) {
						if(l == 0) {
							linkedList.add(j);
						}
						else {
							sum += linkedList.poll();
							linkedList.add(sum);
						}

					}
					sum = 0;
				}
			}

			System.out.println(linkedList.getLast());
			linkedList.clear();

		} // for End
	} // Main End
} // Class End