백준 1932번의 동적계획법 문제를 풀었는데요

kmc04의 이미지

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
 
int cost[1001][501];
int dp[1001][501];
int N;
 
int dfs(int pre, int max_idx) {
    if(max_idx >= N)
        return 0;
    if(dp[pre][max_idx] != -1)
        return dp[pre][max_idx];
    int m = 0;
    m = max(m,cost[pre][max_idx] + dfs(pre,max_idx+1));
    m = max(m,cost[pre][max_idx] + dfs(pre+1,max_idx+1));
    dp[pre][max_idx] = m;
 
    return m;
}
 
int main()
{
    scanf("%d",&N);
    for(int i=0; i<N; i++)
        for(int j=0; j<=i; j++)
            scanf("%d",&cost[j][i]);
    memset(dp,-1,sizeof(dp));
    printf("%d\n",dfs(0,0));
    return 0;
}

재귀호출 과정에서 dp 에 m이 어떤과정을 거쳐서 저장되는지 잘 모르겠습니다 ..
m = max(m,cost[pre][max_idx] + dfs(pre,max_idx+1));
m = max(m,cost[pre][max_idx] + dfs(pre+1,max_idx+1));
이렇게 두번 재귀호출을 하는데

둘 중에 큰값이 dp[pre][max_idx]에 저장되는 것인가요?
아니면 각각 별개로 저장되고 진행되고 저장되고 진행되고 하는것인가요

간략하게나마 설명해주실 고수분 부탁드립니다 ㅜㅜ

File attachments: 
첨부파일 크기
Image icon K-58.png39.86 KB
raymundo의 이미지

"각각 별개로 저장되고 진행되고 저장되고 진행되고"가 무슨 뜻인지 모르겠습니다만, 코드만 보면 결국
- m 의 초기값
- cost[pre][max_idx] + dfs(pre,max_idx+1)
- cost[pre][max_idx] + dfs(pre+1,max_idx+1)
셋 중의 가장 큰 값이 m에 들어가고 다시 dp[pre][max_idx]에 들어가겠죠.

물론 dfs(pre,max_idx+1)을 구하려니 다시 입력의 다음 줄에서 같은 과정을 먼저 수행할 테고, 그러자면 또 다다음 줄에서 같은 과정을 먼저... 이러다보면 결국 제일 아랫줄부터 구해서 위로 쌓아올리게 될 거고요.

프린트문 하나만 추가해서 천천히 따라가보시면 이해하시는데 도움이 될 것 같습니다.

    dp[pre][max_idx] = m;
 
    printf("dp[%d][%d] = %d\n", pre, max_idx, m);

좋은 하루 되세요!

세벌의 이미지

백준 님에게 물어보세요.

텍스트로 칠 수 있는 건 화면 캡처해서 첨부하는 대신 직접 쳐서 본문에 넣는 게 좋습니다.

익명 사용자의 이미지

난 도저히 모르겠음.
세벌의 답변이 shint의 그것과 비교했을 때, 정말 나은지.....
세벌이 shint에게, 그런 답변 달지 마라 할 수 있는지......

익명 사용자의 이미지

동족혐오인가보죠 뭐. 그런 건 아무래도 상관없습니다.

양질의 답변을 바란다면, 양질의 답변을 쓰면 되는거에요.

Quote:
Be the change that you want to see in the world.
jick의 이미지

뭐 맨날 보는 저로서는 그냥 저 사람 스타일인갑다 하는데, 생전 첨 오는 사람이 질문했다가 "그건 원저자한테 물어보시구요 코드는 이미지로 올리지 마세요" 같은 답변 들으면 좌절해서 다시 안 올까봐 좀 안쓰럽긴 합니다.

...뭐 하긴 코더는 원래 강하게 커야 하니 그정도로 좌절할 거면 그만두는 게 나을지... 음 이건 아닌가? -_-

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.