글 읽기 - 이 문제 k범위 맞나요??

112224 5년 전 0

1<=k<=20 이라고 해서 배열사이즈 2^21= 2097152 에다가 + 8 해서 사이즈 잡으니 런타임에러가 나오네요.

이상하다 싶어서 2^22 보다 크게 잡아주니까 맞는데

높이가 k 일 때 엣지의 갯수는 2^(k+1) -2 개 니까. 저 갯수가 모자라서 런타임 에러가 나오지는 않아야 맞는 것 같은데

혹시 데이터에 잘못된 부분이 있을까요?

    int a[2097160];
.......
    int k;
    cin>>k;
    int tmp=(1<<(k+1));
    int top=1;
    for(int i=2;i<tmp;i++)
    {
        cin>>a[i];
    }

doju 5년 전 1

전체 코드를 올려 주세요.

112224 5년 전 0

확인이 늦었습니다 죄송합니다 ㅠㅠ

문제되는 부분은 찾아서 해결이 되었습니다.

답변해주려 하셔서 감사합니다!

// 런타임
#include<iostream>
#include<vector>
using namespace std;

int a[2097160];

int M(int node,int li)            //li는 limit으로 main 문 안의 tmp(2^(k+1))을 넣어줬습니다.
{
    if(node>=li)
    return 0;
    
    /*if(node>li/2)
    return 0;            //리프노드의 경우 함수를 종료(예상 해결방안)
    */
    int ret;
    int lsum=M(node*2,li)+a[node*2];    //
    int rsum=M(node*2+1,li)+a[node*2+1];    //
    int diff;
    if(lsum<rsum)                
    {
        diff=rsum-lsum;
        a[node*2]+=diff;        //
    }
    else
    {
        diff=lsum-rsum;
        a[node*2+1]+=diff;     //
    }
    ret=max(lsum,rsum);
    return ret;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    
    int k;
    cin>>k;
    int tmp=(1<<(k+1));
    int top=1;
    for(int i=2;i<tmp;i++)
    {
        cin>>a[i];
    }
    M(1,tmp);
    int ans=0;
    for(int i=2;i<tmp;i++)
    {
        ans+=a[i];
    }
    cout<<ans<<'\n';
}

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

문제

문제

출처

ICPC

이 문제 k범위 맞나요??

112224 5년 전 0

doju 5년 전 1

112224 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말