[BOJ] 4811 알약 C++

• 문제 설명
• 해결 과정
• 코드 전문

 

문제 설명

 

 

본 문제는 백준의  4811번 알약 문제입니다.

 

약통에는 n개의 알약이 있으며 완전한 알약 하나를 반으로 쪼개서 먹어야합니다.

완전한 약을 골랐을 경우 반쪽으로 쪼개서 반쪽을 먹고 남은 반쪽은 다시 약통에 넣습니다.

 

이 때 약통에 있는 약을 매일 반쪽 씩 복용할 때 고른 알약의 경우의 수 입니다.

 

 

 

 

해결 과정

 

약통에 완전한 알약만 있을 경우 

약통[n(완전한 알약 수) - 1][(반쪽 알약 수) 0 + 1]

.반쪽 알약 수의 0은 완전한 알약만 있기에 0이고 뒤의 +1은 온전한 알약을 선택한 뒤

반쪽은 먹고 반쪽은 약통에 넣었기 때문

 

약통에 반쪽 알약만 있을 경우

1

 

약통에 완전한 알약, 반쪽 알약 둘 다 있을 경우

완전한 알약을 고른 경우

약통[n(완전한 알약 수) - 1][m(반쪽 알약 수) + 1]

반쪽 알약을 고른 경우

약통[n(완전한 알약 수)][m(반쪽 알약 수) - 1]

이 두 경우를 합친 것과 같습니다.

 

 

 

 

코드 전문

 

 

#include <iostream>

using namespace std;

unsigned long long dp[35][35] = { { 0,  }, };

int main() {
    for (int i = 0 ; i < 31; i++) {
        dp[0][i] = 1;
    }

    for (int i = 1 ; i < 31; i++) {
        for (int j = 0 ; j < 31; j++) {
            if (j == 0) dp[i][j] = dp[i-1][j+1];
            else dp[i][j] = dp[i-1][j+1] + dp[i][j-1];
        }
    }

    while (1) {
        int n; 
        cin >> n;
        if (n == 0) return 0;
        cout << dp[n][0] << '\n';
    }
}

 

 

 

 

느낀 점 (잡설 99% , 배운점 1%(많은 편))

 

 

 

DP는 역시 어렵네요.

 

 

 

 

 

긴 글 읽어주셔서 감사합니다. 

부족한 점이 있다면 부디 알려주시면 감사하겠습니다.