sgc109   1년 전

처음엔 꼬지않은 단순한 문제라고 생각해서 단숨에 코드를 작성해서 예제 입력을 쳐넣어보았는데

4바이트로 표현할 수 있는 수를 초과 한것을 알게되어, 알고보니 long long 까지 초과해 버리는 경우도 있다는 것을 알았습니다.

그래서 일반적인 정수 계산으로는 안될것같아서(C++ 에 long long 보다 더 많은 바이트를 사용하여 정수계산을 하는 방법이있나요..?)

int 를 string 형태로 변환하여 계산하는 방법을 사용해야 겠다고 생각을 했습니다.


그래서 관련 STL 이 있나 구글링을 해봤는데 찾지못하여(만약 있다면 가르쳐주시면 감사하겠습니다) 직접 구현을 했습니다..


구현을 하여 제출을 해보니 틀렸다고 나왔습니다.. 허나 아무리 찾아봐도 틀린부분을 찾지 못하였기에 도움을 받고자 질문을 올립니다! 감사합니다.


+p.s. 그리고 보통 이런 문제의 경우 n 이 0 일 때 1가지로 보는것이 맞나요? 1가지 일 것 같기는 하나 혹시 몰라 0가지로 뜨게 만들어봐도 틀렸다고 나왔습니다..


@hongjun7

appa   1년 전

1. 테스트 케이스를 입력받으셨네요.

2. 2배하는 연산은 긴자리 덧셈으로 하셔야 더 빠르겠죠?

sgc109   1년 전

@hongjun7

테스트 케이스를 입력받는다는 말이 명시되어있지않으면 EOF 받으면 끝나도록 하는거였군요...

감사합니다! 그런데 hongjun 님 께서 실전에서 이런 문제를 보셨다면 어떻게 하실건가요??

대회에서 저처럼 직접 긴자리 연산 함수를 직접 구현하면 상당히 시간을 잡아먹을것같은데..

STL 에 이런 기능을 하는 함수가 있나요?

appa   1년 전

긴자리 덧셈은 코딩이 꽤나 쉬운편이고 긴자리 곱셈도 저는 카라츠바 알고리즘을 몇 번 연습해서 짜보았기 때문에 큰 거부감은 없을 것 같습니다.

STL에서 별도로 제공해주는 함수는 없는 걸로 알고있습니다.

나눗셈이나 뺄셈과 같이 약간은 실수할 여지가 있는 것들은, icpc의 경우에는 팀노트에 다 담아가는 편입니다.

아무래도 본 문제처럼 긴자리 연산 언급이 없는데 long long 범위를 넘어간다면 답을 잘못 구한 것은 아닌지, 수학적으로 long long 범위를 넘어가는지 확인합니다. (저 문제에는 예제를 통해 긴자리 연산이 꼭 필요하다는 것을 알려주고 있긴 하지만...)

또 답은 long long 범위 안이라도, 연산 도중에 long long을 넘어가는 경우도 있는데 그런 경우에는 일반적으로는, 계산을 '잘' 하면 처리가 되더라구요.

공식 대회들은 일반적으로 긴자리 연산을 하지 않고도 풀 수 있도록 나머지 값을 주는 걸로 알고있습니다.

sgc109   1년 전

@hongjun7

그렇군요.. 완벽한 답변 감사드립니다!!

baekjoon   1년 전

저는 저런 경우면 Java의 BigInteger를 사용합니다.

sgc109   1년 전

baekjoon 자바에서는 C++ 에서 보다 좀 더 큰수를 다루는 것이 가능하다고 들었는데 그렇군요..


C++ 에서는 역시 직접 구현하는방법밖에 없을까요?

baekjoon   1년 전

다른 사람이 만들어 놓은 것을 사용해도 좋을 것 같아요

http://stackoverflow.com/questions/4507121/c-big-i...

http://codeforces.com/blog/entry/16380


sgc109   1년 전

baekjoon (C++의 경우) 실제 대회에서는 팀노트에 적어가거나 해서 직접 빠르게 구현하는 방법을 사용해야 하겠죠??


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