백준 2775번 "부녀회장이 될테야"

Question:

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

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

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

Input:

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

Output:

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

Restriction:

1 ≤ k, n ≤ 14

Example Case:

Input: 2 1 3 2 3

Output: 6 10

풀이 과정:

이 문제는 시행착오가 많았던 문제이다. 수학적으로 접근하는 문제인데,규칙성을 찾고-시그마 공식을 이용하면 각 층마다의 원소 값을 구할 수 있을 것 같아 처음 풀이방향을 그 쪽으로 진행하였다. 그런데 각 층마다 규칙성이 존재하긴하지만, 층마다 다 달라 일반식을 이끌어 낼 수 없었다…

그래서,문제의 조건을 다시 읽어보자. “a층의 b호에 살려면,자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합” 이 문장에 집중해야 한다. 예를 들면, 0층의 원소값은 전부 호수에 따라 값이 정해진다.

example) arr[0][i] = i (i= 1 ~ 14 *호수. 인덱스 값은 다름)

중요한것은 1층 이후의 호수 원소값인데, 앞서 문장에 따라 그대로, 하나의 합 변수에 이전 층의 호수 원소값을 다 더하면 된다.

example arr[3][5] 의 경우 sum = arr[2][0] + arr[2][1] + … + arr[2][5] 이다.

또한 층이 변할때마다 이 변수의 값은 초기화가 되야한다.(바로 밑 층의 원소값의 합을 원하기 때문에.) 이러한 방법으로 답을 구할 수 있다.

코드 (python 이용…)

arr = [[0]*15 for _ in range(15)] #2차원 배열 생성 - 초기화

for k in range(15): #2차원 배열 안 원소 삽입 1
    arr[0][k] = k+1 #0층의 원소는 전부 호의 숫자와 같다.
    arr[k][0] = 1 #각 층마다의 1호는 원소값이 다 1이다.

sum = 0
for l in range(1,15): #2차원 배열 안 원소 삽입 2
    for e in range(1,15):
        sum += arr[l-1][e-1] + arr[l-1][e]  #l의 e호의 원소값은 바로 아래층인 l-1층의 e-1호,e호의 원소 합
        arr[l][e] = sum #원소값 삽입
        sum -= arr[l-1][e] #두번 더해지는 원소값 빼기 (ex.arr[0][0]+ arr[0][1] => sum 넣고 arr[0][1] 빼야지 다음 원소값에 이중 덧셈 방지)
    sum = 0 #층 변환시 시그마 값 초기화

T = int(input()) #테스트 케이스 개수

for i in range(T):
    K = int(input()) #층
    N = int(input()) #호
    print(arr[K][N-1])  #N-1은 인덱스 조정.(호수)

Conclusion 하나의 방법만 생각해보지말고, 코딩에 익숙하지 않아 문제를 풀 때 너무 복잡하게 풀려고 하는거 같다. 다른 방법도 다양하게 생각해보자.

• 에러 및 숙지할 점

  1. indexerror

  = 문제 조건 숙지하지 못해, 호수가 14인 경우를 빠트리고 배열을 선언하였다.(총 크기가 15여야하는데, 14로 선언)

  2. 파이썬 2차원 배열 선언 및 초기화

  = array = [[초기화 할 값] *열의 개수 for _ in range(행의 갯수)] 이러면 초기화 동시에 선언도 되고 얕은 복사 문제를 피할 수 있다.

• 백준
• 문제풀이