작성일 : 18-05-11 00:47
격자상의 경로 메모리 과다
 글쓴이 : 양진혁(yangjh05)
조회 : 228  
#include <stdio.h>
#include <algorithm>

using namespace std;

double f(int a){
    if(a == 0) return 1;
    return a*f(a - 1);
}

int main()
{
    int N, M, K;
    double ans;
    scanf("%d %d %d", &N, &M, &K);
    if(K == 0){
        ans = f(N + M - 2) / (f(N - 1) * f(M - 1));
        printf("%d", (int)ans);
    } else {
        int x, y;
        y = (K / M) + 1;
        x = K - M * (y - 1);
        ans = (double)((f(x + y - 2) / (f(x - 1) * f(y - 1))) * (f(M + N - x - y) / (f(M - x) * f(N - y))));
        printf("%d", (int)ans);
    }
    return 0;
}
메모리 과다가 어디서 일어나는지 알고 싶어요. 실제 프로그램은 33KB던데...

양진혁 18-05-11 01:21
 
#include <stdio.h>

int D[40][40];
int x, y;
int N, M, K, ans;

int way(int fx, int fy){
    if(fx == 1 || fy == 1) return 1;
    if(fy > N || fx > M) return 0;
    if(D[fx][fy]) return D[fx][fy];
    return D[fx][fy] = way(fx - 1, fy) + way(fx, fy - 1);
}

int main()
{
    scanf("%d %d %d", &N, &M, &K);
    if(K == 0) ans = way(M, N);
    else {
        double tmp;
        tmp = (double)K / (double)M;
        if(tmp - (int)(K / M) > 0) y = (K / M) + 1;
        else y = K / M;
        x = K - M * (y - 1);
        ans = way(x, y) * way(M - x + 1, N - y + 1);
    }
    printf("%d", ans);
    return 0;
}
이게 제대로 된 답인데... 그것도 맞지 않나요...?
컴스쿨 18-05-17 14:22
 
아래의 프로그램중

 if(D[fx][fy]) return D[fx][fy];

이 부분을 보면 해당 위치에 이미 호출해서 값이 구해진 기록이 있으면 다시 호출하지 않습니다.

하지만 위의 코드는 같은 위치를 계속 반복해서 호출을 하게 되므로 스택메모리 공간이 부족하게 됩니다.
 
 

Total 597
번호 제   목 글쓴이 날짜 조회
597 강좌 결제했는데 포인트 적립이 안 이채은 10-15 3
596 입금확인 부탁드려요~~ 장승혁 10-02 19
595 책을 어디서 사놔요? 남지윤 09-01 78
594 15년 초등 4번문제 질문입니다 안성호 08-31 80
593 도와주세요 남지윤 08-20 101
592 맛보기 영상이 재생이 안되요 남지윤 08-18 100
591 문자열2 형성평가5 번 (1) 정주영 07-28 140
590 자기주도 c언어 함수3-4번 문제 (1) 만수 06-19 209
589 입금 확인 부탁드립니다. (1) 이홍국 06-14 164
588 수강연장규정 (1) 허종 06-12 135
587 입금확인 부탁드립니다. (1) 윤일용 06-10 154
586 입금했습니다. (1) 장상우 05-29 127
585 강의 오류 (1) 양진혁 05-27 180
584 2012 중2 전시장 (1) 양진혁 05-21 193
583 입금확인부탁드립니다. (1) 김필애 05-19 117
582 2017년 중등부 2번 (1) 양진혁 05-17 143
581 격자상의 경로 메모리 과다 (2) 양진혁 05-11 229
580 2017전국대회 강좌신청 (1) 김선이 05-10 177
579 중등부 트리 2 (2) 양진혁 05-06 165
578 중등부 트리 (1) 양진혁 05-06 178
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  

회사소개 | 개인정보처리방침 | 이용약관 | 찾아오시는 길 | 이메일주소 무단수집거부 | 사업자정보확인
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호 한컴에듀케이션(주) TEL : 031-388-8840 FAX : 031-388-0996
대표자 : 김동규 사업자번호 : 130-86-02870 통신판매업신고번호 : 제 2010-경기안양-888호
COPYTIGHT(C) 한컴에듀케이션(주), ALL RIGHT RESERVED.
담은강좌 : 0