02402025년 7월 16일

개발

[백준] 2775 - 부녀회장이 될테야

문제 링크 : https://www.acmicpc.net/problem/2775

문제 탐색하기

1) 문제 분석

a층의 b호 인원 수 = 자신의 아래층(a-1)층의 1호부터 b호까지 사람들의 수의 합
0층의 i호에는 i명이 산다.
3층 : 1 / 5 / 15 / 25 / 60
2층 : 1 / 4 / 10 / 20 / 351층 : 1 / 3 / 6 / 10 / 150층 : 1 / 2 / 3 / 4 / 5

2) 가능한 시간복잡도

(1) 입력 처리

테스트 케이스를 입력 -> O(1)
각 테스트 케이스마다 k와 n을 입력 (총 T개) O(2 * T) -> O(T)

(2) DP 테이블 생성 및 초기화

2차원 배열 생성 (층 : k+1, 호수 : n+1)
배열 전체를 0으로 초기화 -> O(k * n)

(3) 0층 초기화

0층은 1호부터 n호까지 채우므로 -> O(n)

(4) DP 테이블 채우기

1층부터 k층까지, 각 층마다 1호부터 n호까지 채우므로
이중 반복문-> O(k * n)

(5) 테스트 케이스 결과 출력

각 테스트 케이스마다 출력 -> O(T)

(6) 전체 시간복잡도

입력 처리 : O(T)
2차원 배열 초기화 : O(k * n)
0층 초기화 : O(n)
DP 테이블 채우기 : O(k * n)
테스트 케이스 별 결과 출력 : O(T)
전체 시간 복잡도 : O(T + T * (k+n + n + k*n))-> 총합 : O(T * k * n)

3) 알고리즘 선택 이유

이 문제는 이전에 계산한 값을 재사용할 수 있다는 특징을 갖고 있었다. 특히, 현재 집의 인원 수를 계산할 때 항상 왼쪽 집과 아래 층 같은 호수의 집의 값을 이용하기 때문에, 중복되는 하위 문제가 반복적으로 등장한다.
따라서, 계산한 값을 저장하고 재사용하는 동적 프로그래밍(DP) 접근이 가장 적합하다고 생각했다.
각 층과 호수를 이중 배열로 관리하고, 점화식(이전 값 이용)을 통해 반복적으로 채워가면 효율적으로 문제를 해결할 수 있을 것 같았다.

잠깐! Dynamic Programming(DP, 동적 프로그래밍)에 대한 간단한 설명, 그리고 관련 예시 문제는 여기를 참고하자.

코드 설계하기

1. 실행 구조

1) 입력 처리

첫 번째 줄에서 테스트 케이스 개수(T)를 입력받는다.
그 다음부터 T개 케이스에 대해 한 케이스당 k와 n을 입력받는다.
각 케이스마다 k와 n을 저장할 배열(또는 객체)을 준비한다.

2) DP 테이블 초기화

0층부터 k층까지, 1호부터 n호까지 사람 수를 저장할 2차원 배열(dp)을 준비한다.
0층은 각 호수에 i명씩 사는 규칙이므로, 0층을 초기화한다.

3) 점화식 기반 DP 테이블 채우기

점화식:dp[k][n] = dp[k][n-1] + dp[k-1][n]
1층부터 k층까지, 1호부터 n호까지 위의 점화식을 반복해서 테이블을 채운다.

4) 결고 출력

각 테스트 케이스마다 dp[k][n]을 출력한다.

2. 고민이 되었던 부분

1) 점화식 세우기 / 0층 고려

점화식을 어떻게 찾을 수 있을지가 제일 고민이었다. DP를 구현할 때, bottom-Up에 사용될 점화식만 세워진다면, 구조를 세우는 부분은 크게 어렵지 않을 것이라 생각했다. 하지만, 생각보다 점화식을 찾는 과정은 어려웠다.

단순히 이전의 값을 사용하는 느낌 보다는, 1차원 배열이 아닌 2차원 배열을 고려해야 했었다. 쉽게 말해, 이중 반복문으로 접근하여 배열 내부에 있는 이전의 값을 사용하는 구조를 고려해야 했던 점이 어려움으로 다가왔었다.

- 3층 : 1 / 5 / 15 / 25 / 60 - 2층 : 1 / 4 / 10 / 20 / 35 - 1층 : 1 / 3 / 6 / 10 / 15 - 0층 : 1 / 2 / 3 / 4 / 5

그래서 가장 일차원적으로 접근했다. 0층의 경우 1부터 n까지 숫자가 1씩 증가하는 구조로 시작되기에, 이를 먼저 고려했고, 문제에서 제공해준 조건에 맞춰서 1, 2, 3층의 인원 수를 작성해봤다. 그 결과 각 방의 인원 수는 옆방의 인원수 + 한 층 아래의 자기 위치 호수의 인원 수라는 점을 알게 되었다.

dp[k][n] = dp[k][n-1] + dp[k-1][n]

이를 통해서 이와 같은 점화식을 도출해낼 수 있었다. 하지만, 더 고려해야 할 점이 있었다. 바로 0층의 경우에는 점화식에 해당되지 않았기 때문이다. 그러나 이 부분도 쉽게 솔루션을 도출해낼 수 있었다. 이중 반복문으로 점화식을 사용하기 전에, 미리 0층에 대한 값을 1차 반복문을 통해서 삽입해놓은 뒤에, 이중 반목문을 실행하면 0층의 방 별 인원 수를 사용할 수 있었다.

2) 탑다운 방식

앞서 내가 생각한 방법은 Bottom-Up 방식이었다. 그러나 DP는 Top-Down 방식도 가능하기에, 어떻게 하면 이 방식으로 구현할 수 있을지에 대해서도 고민해볼 수 있었다. 재귀 함수를 선언하고, 0층이면 바로 n을 반환하고, 1호면 1을 반환하는 두 가지 조건문을 둔 뒤에, 이 둘의 경우가 아니라면 왼쪽 집 + 아래층 같은 집의 값의 합으로 계산한 뒤, 이미 계산된 값은 memo에 저장하여 재사용하는 방법을 사용하면 될 것 같았다. 그래서 아래의 코드도 첨부하게 되었다.

JavaScript

function getMembers(testCase) {
    const k = Number(testCase.k);
    const n = Number(testCase.n);

    // 메모이제이션용 2차원 배열 생성
    const memo = Array.from({ length: k + 1 }, () => Array(n + 1).fill(undefined));

    // 재귀 함수
    function dfs(floor, room) {
        if (floor === 0) return room;  // 0층이면 n호에 n명
        if (room === 1) return 1;      // 모든 층에서 1호는 항상 1명

        if (memo[floor][room] !== undefined) {
            return memo[floor][room];  // 저장된 값 재사용
        }

        // 점화식 적용 후 저장
        memo[floor][room] = dfs(floor, room - 1) + dfs(floor - 1, room);
        return memo[floor][room];
    }

    return dfs(k, n);
}

정답 코드

JavaScript

// 사용 언어 : Javascript

// 입력 처리
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

const repeatCount = Number(input[0]);
input.shift();
input.map(Number);

// 테스크 케이스 클래스
class testCase {
    constructor(k, n) {
    this.k = k;
    this.n = n;
    }
}

// 테스트 케이스 담기
let test = [];
for (let i = 0; i < input.length; i += 2){
    test.push(new testCase(input[i], input[i + 1]));
}

// 인원 수 구하는 함수
function getMembers(testCase) {
    let k = testCase.k;
    let n = testCase.n;

    if (n === 1) return 1;
    if (n === 2) return k + n;

    // 2차원 배열 초기화
    const dp = Array.from({ length: k + 1 }, () => Array(n + 1).fill(0));
    
    // 0층 초기화
    for (let i = 1; i <= n; i++){
        dp[0][i] = i;
    }

    // DP 테이블 채우기
    for (let floor = 1; floor <= k; floor++){
        for (let room = 1; room <= n; room++){
            dp[floor][room] = dp[floor][room - 1] + dp[floor - 1][room];
        }
    }

    // k층 n호 인원 수 반환
    return dp[k][n];
}

// 테스크 케이스 별 결과 출력
for (let i = 0; i < repeatCount; i++){
    console.log(getMembers(test[i]));
}

마무리하며

문제를 풀면서 다시 한 번 “생각 후 코딩”의 중요성을 깊이 체감할 수 있었다. 처음에는 바로 코드를 작성하고 싶었지만, 조금만 더 문제를 분석하고 접근 방식을 정리하는 과정이 얼마나 중요한지 이번 문제를 통해 다시금 깨닫게 되었다.

특히, 이번 문제처럼 조건이 간단해 보이지만 실제로는 누적합이나 점화식을 고민해야 하는 경우, 무작정 구현하기보다는 문제의 구조를 먼저 파악하는 것이 훨씬 효율적인 해결로 이어진다는 점을 경험할 수 있었다.

무엇보다 문제 풀이 자체도 중요하지만, 그 안에서 내가 부족한 부분과 더 깊게 고민할 수 있는 포인트들을 찾는 과정이 스스로에게 의미 있는 배움이 된다고 느꼈다. 앞으로도 단순히 정답을 맞추는 것을 넘어서, 어떻게 더 나은 방식으로 접근하고 해결할 수 있을지 고민하는 습관을 꾸준히 키워나가고 싶다.

최근 글