글 읽기 - 다이나믹 프로그래밍

inhoj123 5년 전 2

다이나믹 프로그래밍 초짜입니다.

다이나믹 프로그래밍이 정확히 무엇인지와 몇가지 팁 정도만 알려주시면 감사하겠습니다.

그리고 이왕이면 아래 소스 문제좀...(메모리 초과/시간 초과이니 특히 프로그램 최적화 팁좀 알려주세요)

아니면 문제 접근 방식 지적도 좋습니다.

#include<stdio.h>

class input_ //입력밭는 변수
{
public:
    short x[3];
}*input;
class calcul //tf:만약 cal[20][302].tf 가 true 면 20번째 집까지 302원이 소비될 수 있음
{
public:
    bool tf;
    short color; // color:cal[20][302].color 가 만약 1 이면 20번째 집, 
                 //302 원이 소비된 상황에서 1번째 색이 쓰임.
    calcul(){tf=0;}
}cal[41][1000001]; //설명 참조
int main()
{
    short T;
    scanf("%d", &T);
    input=new input_ [T];
    for(short a=0;a<T;a++)
    {
        scanf("%d %d %d", &input[a].x[0], &input[a].x[1], &input[a].x[2]);
    }//입력
    cal[0][0].tf=1;
    cal[0][0].color=3;//밑작업. cal[0][0] 이 시작할 곳이므로
                      //color이 3 인 이유는 0번째 집은 색깔 계산을 하지 않기 위해서임.
    for(short a=0;a<T+1;a++)
    {
        for(int b=0;b<1000001;b++)
        {
            if(cal[a][b].tf==0) continue;
            else{
                if(b+input[a].x[0]<=1000*T&&cal[a][b].color!=0) //만약 다음 집과 색깔이 겹치지 않고,
                                                        //최대 비용을 넘지 않으면 cal[집][비용].tf=1
                    cal[a+1][b+input[a].x[0]].tf=1; cal[a+1][b+input[a].x[2]].color=0;
                if(b+input[a].x[1]<=1000*T&&cal[a][b].color!=1)
                    cal[a+1][b+input[a].x[1]].tf=1; cal[a+1][b+input[a].x[2]].color=1;
                if(b+input[a].x[2]<=1000*T&&cal[a][b].color!=2)
                    cal[a+1][b+input[a].x[2]].tf=1; cal[a+1][b+input[a].x[2]].color=2;
            }
        }
    }
    for(int a=0;a<1000001;a++)
    {
        if(cal[T][a].tf==1)
        {
            printf("%d", a);
            return 0;
        }
    }//가장 적은 비용 찾기
    delete input;
    //글쓴이의 두뇌부족으로 설명 빈약
}

cpp05013 5년 전 1

[41][1000001]은 너무 큽니다. 이렇게나 많이 쓸 필요가 없습니다. 왜 41이고 1000001인지, 어떻게 접근하셨는지 설명해 주세요.

inhoj123 5년 전 1

저도 그렇게 생각합니다만...(메모리 초과)

1000000이라는 숫자는 최대로 나올 수 있는 비용의 양입니다.

cal[집 수][최대 비용 수 or 집*1000(집 하나당 최대로 나올 수 있는 비용)] 에서

만약 cal[21][8324].tf==1 이면 21번째 집에서 8324원이 나올 수 있다는 뜻이고, cal[21][8324].tf==0 이면 그 반대입니다.

koi/2017/초등부 3번 문제 답안을 참고해서 풀었는데 메모리가 생각보다 (상상을 초월) 많이 나오더라구요..

이런 문제는 어떻게 접근해야 하죠?(설명이 부실한 점 죄송합니다)

moonhi123 5년 전 1

안냐세요!

일단 다이나믹 프로그래밍은 큰 문제를 작은 문제로 나눠서 풀고, 중복을 제거(메모이제이션)하여 일반 제귀보다 훨씬 빠르게 됩니다.

소스는 설명이 안달려있어 자세히는 모르겠습니다만은, 초짜라면 님이 푼 소스같이 BOTTOM - UP방식(대체로 for문) 보다는 제귀함수 + 메모제이션을 이용한 TOP-DOWN방식이

훨씬 쉽습니다.

http://coding-all.tistory.com/...

저희 블로그인데 참고하시면 좋을 것 같습니다.

P.S 보아하니 KOI 초등부 나가시는 것 같은데(중학생이시면 죄송...) 저도 KOI 초등부 나갑니다!

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

문제

문제

출처

ICPC

다이나믹 프로그래밍

inhoj123 5년 전 2

cpp05013 5년 전 1

inhoj123 5년 전 1

moonhi123 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말