결국 문자열 영역에서 나눗셈을 처리해야하는데
반복빼기 나누기 알고리즘 썼다간 1E1000/1 걸려서 개박살나는 (...) 엔딩밖에 없어서 이것보다는 효율적인 알고리즘을 써야합니다.
한번 그냥 Long Division 으로 덤벼볼까요.
1271번 - 엄청난 부자2
결국 문자열 영역에서 나눗셈을 처리해야하는데
반복빼기 나누기 알고리즘 썼다간 1E1000/1 걸려서 개박살나는 (...) 엔딩밖에 없어서 이것보다는 효율적인 알고리즘을 써야합니다.
한번 그냥 Long Division 으로 덤벼볼까요.
[파이썬]에서는 입력받고 n // m, n % m하면 쉽게 풀립니다
.....................................................................
댓글을 작성하려면 로그인해야 합니다.
ssskid 2년 전 5
타 언어에서의 이 문제 난이도는 실버 이상급이라 생각합니다만, 파이썬의 존재 때문에 브론즈 5에서 쉽사리 올라갈 것 같지는 않네요.
따라서 투자한 노력 대비 얻어지는( solved.ac 브론즈 5짜리) 가성비가 굉장히 낮은 코드라서 이건 적당한 수준의 팁을 드리는게 맞다고 생각해서 주의 문구 달고 스포성 게시물 올립니다.
10의 1000제곱까지 나가면 1001자릿수까지의 계산이고, 이건 천문학적 단위로(존재 가능한 평행우주 갯수 정도에서나 언급되는) 일반적인 언어에서 절대절대절대로 지원하지 않는 계산단위입니다.
파이썬이 되는 건 그건 파이썬이니까 제공하는 거고요;
다들 예상하셨겠지만 초등학교 때 나눗셈 풀 때의 방식을 생각하면 됩니다.
('고작 브론즈 5에 이 노가다 하느니 차라리 안해' 라는 게 C 사용자의 풀이가 저조한 주요 이유로 보입니다만 ^^;)
몫의 최대 자릿수 개수는 어차피 피제수의 자리수 - 제수의 자리수 + 1 자리부터 계산해야 하고,
몫이 9라면, 8이라면, 7이라면... 식으로 문자열을 비교하고 피제수가 제수보다 커지는 수가 몫이 되고,
제수와 몫을 곱한 만큼 피제수에 빼내어 가는 식으로 문자열을 비교해야 합니다.
속도를 위해서는 몫 자릿수 확정하면서 제수에 9~0을 곱하는 연산이 매번 반복되다 보니, 미리 메모리에 2차원배열로 문자열을 만들어 두고 비교하고 피제수가 제수보다 큰 게 확인될 때 해당 값을 문자열에서 빼고 다시 48(아스키 '0')을 더하고 한자리 수 씩 내림하는 식의 접근도 좋겠습니다.
자릿수 올림 내림 같은 변환(5 + 6 해서 1 올려서 윗자리 연산에 변수 넘김, 10으로 나눈 나머지 1에 48을 더해 저장), 출력 시 앞이 0인 자릿 수 삭제나, 이래저래 자디잘고 자디잘고 자디잔 손을 볼 게 많은 코드가 됩니다. 이 부분은 여기저기 찾아보며 도움을 받았구요;
물론 여기 저보다 우수하신 분들이 많은데 C 깨작거렸던게 성공해 놔서 흥분되는 마음 안고 끄적여 봤습니다. ^^; 부디 건승하시길 바라며...