[백준]_1312 번 : 소수(파이썬 and C언어)

 

1312번: 소수

관찰

솔직히 처음 보았을 때는 너무 쉬워 보였다. 하지만 우리의 컴퓨터는 소수점을 잘 다루지 못한다.. 또한 계산할 숫자들의 크기를 조심해야 한다. 일단 a/b의 값을 c에 저장하고 c를 소수점 아래로 쪼개는 방법이 있을 것이다. 하지만 이렇게 할 시 어떤 문제점이 생기는지 확인해 보자.

 

---

시도 1(Python) 

import sys
input=sys.stdin.readline

a,b,n=map(int, input().split())
ls=list(str(a/b))
buffer=ls.index('.')
print(ls[buffer+n])

---

import sys
input = sys.stdin.readline

a, b, n = map(int, input().split())
c = a / b

c*=10**n
print(int(c)%10)

 

<평가> 두 개의 접근 다 우리가 생각하는 방법 그대로 들어간 것이다. 첫 번째 코드는 소수점을 배열로 받아 '.'의 인덱스를 buffer에 저장하고 그 위치에서 얼마나 더 뒤로 가야 하는지(n)까지 포함하여 요소를 찾아 주었다. 하지만 파이썬에서 소수점 아래 15자리까지 밖에 나오지 않는다!! 그래서 탈락.

 

두 번째는  컴퓨터가 10^1000000을 계산해야 할 위험이 있기 때문에 런타임 에러가 발생한다. 따라서 이것도 탈락

전략 변화

자료의 크기가 너무 커질 위험이 크기 때문에 숫자를 통으로 구한 상태에서 계산을 수행하는 것이 아닌 애초에 소수점 아래의 숫자들을 한 개씩 구해가 보자.

우리가 초등학교 때 배웠던 나눗셈 방법을 사용하면 된다!!

 

예를 들어 a=25, b=7, n=2라고 해보자. 25를 7로 나누면 몫이 3이고 나머지가 4이다. 나머지가 존재하기 때문에 연산을 멈추지 않고 4를 40으로 만든다(손으로 써 보면 40으로 만드는 이유를 알 수 있다). 또다시 40을 7로 나눈다. 몫은 5이고 나머지도 5이다. 나머지가 5이므로 다시 50으로 만들어 준다. 다시 50을 7로 나누면 몫이 7이고 나머지가 1이다. 여기서 규칙을 알 수 있는가?! 실제로 25/7을 해보면 3.571428571428..이다. 그리고 n=2이므로 우리가 찾는 답은 7이고 7은 50을 7로 나눈 몫에 해당한다. 따라서 아래와 같은 순서를 도출할 수 있다.

1. (a%b)*10을 a에 저장한다.
2. 1번 과정을 거친 a를 b로 나눈 몫을 result에 저장한다.
3. 위 과정을 n번 반복한다.

따라서 최종 코드는 다음과 같다.

import sys
input=sys.stdin.readline

a,b,n=map(int, input().split())

for _ in range(n):
    a=(a%b)*10
    result=a//b
print(result)

시도 2(C 언어) 

 

#include<stdio.h>
int main()
{
    int a,b,c,gar,result_c;
    scanf("%d %d %d",&a,&b,&c);
    if(c!=1)
    {
        gar=a%b;
        result_c=gar;
        for(int i=0;i<c-1;i++)
        {
            gar=(10*gar)%b;
            result_c=(10*gar)/b;	
        }
        printf("%d",result_c);
    }
    else
    {
        gar=a%b;
        result_c=(gar*10)/b;
        printf("%d",result_c);
    }		    
}

<평가> n=1일 때 if문 안의 조건을 만족하지 않으니까 예외 사항으로 달아 주었다. 그만큼 코드가 길어지고 예쁘지도 않다..

따라서 위의 파이썬 코드처럼 고쳐주자

#include<stdio.h>
int main()
{
    int a,b,n,gar,result_c;
    scanf("%d %d %d",&a,&b,&n);
    for(int i=0;i<n;i++)
	{
		a=(a%b)*10;
		result_c=a/b;
	}
	printf("%d",result_c);		    
}