글 읽기 - 숫자 삼각형!!!!!!! DP 고수 님들 도와주세요!!!!

seanrocket17_2 7년 전 1

예제도 안나오네여..... 도와주세요.....

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
int n, arr[510][510], D[510][510], maxi = -1;

int main()
{
    scanf("%d",&n);
    for (int i = 0; i < n; i++){
        for (int j = 1; j <= i + 1; j++)
            scanf("%d",&arr[i][j]);
    }
    D[0][0] = arr[0][0];
    for (int i = 1; i < n; i++){
        for (int j = 0; j < i; j++){
            if (j == 0)
                D[i][j] = D[i - 1][j] + arr[i][j];
            else if (j == i - 1 && j != 0)
                D[i][j] = D[i - 1][j - 1] + arr[i][j];
            else D[i][j] = max(D[i - 1][j], D[i - 1][j - 1]) + arr[i][j];
        }
    }
    for (int i = 0; i < n; i++)
        maxi = max(maxi, D[n - 1][i]);
    printf("%d",maxi);
}

lee_seulbi 7년 전 1

거의 다 다 푸셨네요!

첫번째. 배열 번호 문제가 있습니다!

arr의 시작은 (0,1)이고 D의 시작은 (0,0)입니다! 이 점을 잘 생각해서 고쳐보세요!

두번째. 각 줄의 0번째와 마지막 번째를 따로 걸러서 하실 필요가 없습니다!

(이 부분을 잘 생각해보세요! arr와 D를 출력해보시면 금방 알 수 있습니다!)

seanrocket17_2 7년 전 1

배열 번호 문제는 arr를 입력 받았을때 for (int j = 0; j < i + 1; j++)로 고쳐서 해결 했는데

두번째로 따로 않 걸러도 된다는 것을 잘 이해 못하겠습니다.

i = 1, j = 0 일때 D[i][j] = max(D[i - 1][j], D[i - 1][j - 1]) + arr[i][j] 를 그대로 이용하면 D[i - 1][j - 1]이 D[0][-1] 이 돼서 런타임 에러가 나지 않을까요?????

아니면 그냥 D의 시작을 (1, 1)로 고치고 arr(1, 1)로 고칠까요??

아무튼 배열 번호 문제부터 고쳐서 예제가 잘 나와서 제출해 보니 틀립니다..도와주세요...

seanrocket17_2 7년 전 2

3분전에 말한 것 처럼 D, arr의 시작을 (1, 1)로 고치고 점화식을 일반화 시키니까 맞았어요!!!

걸러서 하는게 문제가 없을 거라고 생각했는데 그 부분에도 문제가 있었습니다.

아무튼 lee_seulbi 님 굉장히 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

숫자 삼각형!!!!!!! DP 고수 님들 도와주세요!!!!

seanrocket17_2 7년 전 1

lee_seulbi 7년 전 1

seanrocket17_2 7년 전 1

seanrocket17_2 7년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말