BOJ 2775번 : 부녀회장이 될테야

안녕하세요. 지난 포스팅의 BOJ 10250번 : ACM 호텔에서는 이차원 배열을 활용해서 문제를 풀어보았습니다. 오늘도 이차원 배열을 활용해서 문제를 풀어보도록 하죠. 

 

 

완벽한 코딩은 존재하지 않습니다. 제가 제출한 코드 역시 마찬가지고 그저 참고만 해주시길 바랍니다. 

 

핵심 포인트

• 기본 구현능력

 

제출 코드

for _ in range(int(input())) :
    k = int(input())
    n = int(input())
    floor = [[i for i in range(1, n + 1)]]
    for i in range(1, k + 1) :
        line = []
        for j in range(1, n + 1) :
            line.append(sum(floor[i - 1][:j]))
        floor.append(line)
    print(floor[k][n - 1])

 

해설

가장 먼저 입력 형식은 테스트케이스의 개수 $T$를 입력받습니다. 저는 항상 테스트케이스 변수는 나중에 사용하지 않기 때문에 그냥 for 문의 range 함수 안에서 선언하는 편입니다. 그리고 다음으로 $k$와 $n$을 한 줄씩 입력받아주면 됩니다. 입력에서는 그렇게 큰 어려움이 없네요. 

 

이 아파트에는 특별한 규칙이 있습니다. $k$층 $n$호에 거주한다고 가정했을 때 $k - 1$층의 1호부터 $n$호까지 거주하는 사람들의 합만큼의 사람이 거주해야하죠. 이번 문제는 $k$층 $n$호에 거주하는 거주민이 몇 명인지 계산하는 문제입니다. 이때, $k = 0$일 때는 $n$호에는 $n$명의 사람들이 거주하고 있게 됩니다. 기본적으로 이 문제를 재귀적으로 풀 수 있지만, 제출해보니 시간초과가 나더군요. 따라서, 단순 반복문으로 해결해야합니다. 

 

아이디어는 간단합니다. 일단, 0층에서 $1 ~ n$호까지 미리 몇 명이 사는 지 선언해놓는 것으로 시작합니다. 이를 floor 변수라고 하죠. floor 변수에 1층, 2층, ..., $k$층 순으로 각 층에 거주하는 사람들의 명수를 계산하여 저장할 것 입니다. 애초에 $k$층 $n$호에 사는 사람이 몇 명인지 알려면 아랫층이 모두 몇 명인지 알아야하기 때문에 이렇게 계산해주는 것입니다. 

 

그리고 첫번째 반복문은 층을 고정해줍니다. 해당 층수의 $1 ~ n$호까지 사는 사람들의 명수를 저장한 변수를 line 이라고 하겠습니다. 이중반복문이기 때문에 변수에 주의해야합니다. $i$는 층수에 대한 변수이고 $j$는 호수에 대한 변수입니다. 그리고 floor 변수에서 첫번째 인덱스가 층수, 두번째 인덱스가 호수이기 때문에 floor[i][j]란 $i$번째 층의 $j$호수에 사는 사람들의 명수를 의미하죠. 문제에 따르면 $i$층 $j$호에 살기 위해서는 $i - 1$층의 $1 ~ j$호까지의 거주민들의 전체 합을 저장해야합니다. 따라서, sum 함수를 이용해서 미리 지금까지 계산한 floor 변수의 $i - 1$층의 거주민들의 합을 계산해주는 것이죠. 각 호에 대한 계산이 끝나게 되면 line 리스트 자체를 floor에 append 해주면 됩니다. 그리고 마지막 출력은 인덱스가 0부터 시작하기 때문에 $n - 1$로 출력하고 $k$같은 경우에는 이미 0층에 대한 정보를 저장했기 때문에 그대로 사용하면 됩니다. 

 

참고자료 및 그림출처

백준 코딩 문제