900B Position in Fraction

a/b가 주어졌을 때 소수점 아래에 정확히 c가 있는 자릿수 구하기

1<=a,b<=10^5, 0<=c<=9

real math problem... 

ㅠ.ㅠ

난이도가 3/10~ 4/10 정도 되는 것같다.

나눗셈을 수행하여 정확히 충분한 자릿수 까지 구해야한다.

그런데 이게 모호하다.... 

왜냐면 어디까지가 충분한지 모르기 떄문이다.

두 정수들로 주어진 분수 중엔 어떤 분수들은, 순환소수가 아니다. 어떤 분수들은 순환소수이다. 

무리수는 순환소수가 아니며 무한한 소수점 자리를 가지고 있다.

어쨌든, 두 정수로 주어지니까 순환소수이거나 순환소수가 아닐 것인데, 그런데 이게 쉽지가 않다.

double형으로 충분히 저장될까?

내 생각엔 아닐것 같다.

자 그럼 소수점 아래에 몇 자리수까지 체크를 해봐야할까. ㅋ 이게 진짜 거슬려서 풀지못했다.

사실 이 문제를 해결하기 위해 코포 editorial 을 봤는데,  비둘기집의 원리를 사용하면 쉽게 해결할 수 있다고한다.

소수점 자리 체크는 정확히 b만큼 하면된다고 한다. 왜냐하면 우리가 특정지을 수 있는 그  소수점 b 이상의 자리에서 등장할수 없다고 한다. 

왜그럴까 ..ㅋㅋㅋㅋ 난 잘모르겠다.

몇 일간 고민을 했는데, 그리고 아 수학공부를 해야겠다 생각을 했는데, 오늘 위키를 찾아보니 이것이 나온다.

아래 링크 참조.

https://en.wikipedia.org/wiki/Repeating_decimal

여기서 Fractions with prime denominators를 참고해보자. 

보면 정확히 최대 b만큼의 길이의 순환을 가지긴한다. 

그런데 우리가 입력받는것은 gcd가 되어있지 않은 상황.

그래서 gcd를 수행해준뒤 연산을 수행했다. 굉장히 쉬운 연산이였지만 나한텐 익숙하지 않았다.

소스보기

https://github.com/ingyeoking13/algorithm/blob/master/cf/math/900B.c

/

나는 기업 코딩테스트를 중점으로 공부를 해왔지만, 올림피아드 느낌?의 문제에선, 이 문제에서 약간 벽을 느꼈다.

꼬ㅒ 많은 문제를 풀어왔다고 생각했는데, 이런 문제에서 발을잡히니 기분이 조금 그랬다.

씁쓸했다. 공부를 게을리 하면안되는데 이럴경우 뭐 부터 해야할지 조금 허무하다.

프로그래밍 설계? 자료구조? 알고리즘? 수학?

하나하나 놓칠수가 없다고 생각하지만, 하하

/