작성일 : 18-05-11 00:47
격자상의 경로 메모리 과다
 글쓴이 : 양진혁(yangjh05)
조회 : 2,529  
#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 661
번호 제   목 글쓴이 날짜 조회
121 입금확인이요 (1) 윤영주 03-29 2637
120 강좌 (1) 이진명 03-18 2636
119 입금했습니다 (1) 김선태 03-18 2633
118 결제를 어떻게 해야하는건가요?? (1) 김선태 03-15 2626
117 입금 확인 부탁드립니다. (1) 김수란 03-17 2621
116 입금 확인 부탁합니다. (1) 박선하 03-19 2615
115 2017년 정보올림피아드 강좌는 언제 볼수있을까요? (1) 성정모 12-26 2611
114 입금완료했어요 (1) 이형준 12-31 2607
113 입금 확인 부탁드립니다 (1) 류지민 03-17 2605
112 2016전국본선문제풀이 (1) 허종 01-31 2590
111 동영상 화면이 잔상및 노이즈 발생 (1) 김중권 01-26 2577
110 자기주도 c언어 함수3-4번 문제 (1) 만수 06-19 2568
109 결제했습니다. 확인부탁드립니다. 조영재 06-09 2566
108 결재 승인 요청 (1) 신민균 02-09 2559
107 강의를 취소 하고자 합니다. (1) 백광선 03-02 2551
106 입금했습니다 (1) 홍예환 03-13 2534
105 2017년 초등 31번 풀이 과정 중간에 틀렸는데요... (1) 박지훈 03-09 2532
104 격자상의 경로 메모리 과다 (2) 양진혁 05-11 2530
103 입금했습니다 (1) 강효정 03-15 2529
102 입금 확인 부탁드립니다. (1) 김동휘 03-26 2524
 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