글 읽기 - 왜 틀렸는지 잘 모르겠습니다 도와주세요

master1511 7년 전 0

어디가 틀렸는지 잘 모르겠습니다.

#include<stdio.h>
#include<math.h>
int k,n,i,t,ii,tt,c,ct;
int main()
{
    scanf("%d%d",&k,&n);
    if(k==0)//거리가 0인경우 끝
    {
        printf("0"); return 0;
    }
    t=pow((float)2,n);
    /*
    2진법으로 생각해서 0인경우 아래, 1인경우 위 로 생각하였습니다.
    ct는 count temp의 약자로 ct가 k보다 같거나 큰경우(물벼룩이 수면에 올라와 죽음)
    전체 c(count)를 1씩 늘리고 루프를 벗어났습니다.
    */
    for(;i<t;i++)
    {
        ct=0;
        for(tt=i,ii=0;tt;tt/=2)
        {
            if(tt%2==1) ct++;//2진수에서 1인경우 위로
            else ct--;//0인경우 아래로
            
            if(ct>=k)//위로 올라오면
            {
                c++;//c를 하나더해주고
                tt=0;//루프를 벗어남
            }
        }
 
    }

    printf("%d\n",((int)pow(2.0,n)-c));//전체 - 죽을확률=살확률 출력
    return 0;
}

portableangel 7년 전 0

우선, 가능한 모든 경우의 개수가 너무 커 int형 변수인 t에 담을 수가 없습니다. (int 최대값은 2^31-1)

또한 이를 long long 자료형으로 고친다 해도, 연산 횟수가 너무 많아 시간초과가 나게 됩니다.

dynamic programming에 대해 찾아보시는 것을 추천합니다.

master1511 7년 전 0

정말 감사합니다. 말씀해주셧던 동적 프로그래밍을 사용해서 짜봤습니다.

하지만 이번에도 틀렸다고 나오네요...어느 부분이 문제인걸까요..

바쁘신데 번거롭게 해드려 죄송합니다.

#include<stdio.h>
#include<math.h>
int k,n;
unsigned long long arr[64][64]={0};
int ze(int n,int k)
{
    if(n<k)
        return 0;
    if(n==k)
        return arr[n][k]=1;
    if(k==0)
        return arr[n][k]=(int)pow(2.0,n);
    if(arr[n][k]!=0)
        return arr[n][k];
    else
        return arr[n][k]=ze(n-1,k-1)+ze(n-1,k+1);
}
int main()
{
    scanf("%d%d",&k,&n);
    if(n==0)
	{
        printf("0"); return 0;
	}
    ze(n,k);
    printf("%lld",(long long)pow(2.0,n)-arr[n][k]);

    return 0;
}

portableangel 7년 전 0

ze 함수의 반환값이 int로 되어 있는데, 오버플로가 날 것 같습니다.

또한 pow 함수로 실수를 계산하는 과정에서 어떤 오차가 있을 지 모르니, 2^n을 사용하고 싶으시다면 (1LL<<n)과 같이 정수로 사용해주시는 편이 안전합니다.

master1511 7년 전 0

다 고쳤는데도 틀렸다고 나오네요..

대채 어디에 제가 보지못한 실수가 있는걸까요......ㅠ

#include<stdio.h>
int k,n;
unsigned long long arr[64][64]={0};
unsigned long long ze(int n,int k)
{
    if(n<k)
        return 0;
    if(n==k)
        return arr[n][k]=1;
    if(k==0)
        return arr[n][k]=(unsigned long long)(2<<(n-1));
    if(arr[n][k]!=0)
        return arr[n][k];
    else
        return arr[n][k]=ze(n-1,k-1)+ze(n-1,k+1);
}
int main()
{
    scanf("%d%d",&k,&n);
    if(n==0)
	{
        printf("0"); return 0;
	}
    ze(n,k);
    printf("%llu",(unsigned long long)(2<<(n-1))-arr[n][k]);
    return 0;
}

yohan5050 7년 전 0

위에 portableangel님이 적어두신 것 처럼

2<<(n-1)이 아니라 2LL<<(n-1)로 하셔야 합니다.

저도 정확히 알지는 못하지만

제가 알기로는 그냥 2로 쓸 경우 int형 정수(32bit)이기 때문에

0000 0000 0000 0000 0000 0000 0000 0010 을 shift left(<<)하는 것이라

아무리 많이 <<해도 int형 범위를 넘어갈 수 없습니다.

그래서 64bit짜리 정수 자료형인 2LL을 가지고 하셔야 합니다.

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

문제

문제

출처

ICPC

왜 틀렸는지 잘 모르겠습니다 도와주세요

master1511 7년 전 0

portableangel 7년 전 0

master1511 7년 전 0

portableangel 7년 전 0

master1511 7년 전 0

yohan5050 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말