코딩테스트(소프티어)_바이러스_2단계

코딩테스트(소프티어)_바이러스_2단계

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId;=407&sw;_prbl_sbms_sn=35184

제한시간 : C/C++(1초), Java/Python/JS(2초) | 메모리 제한 : 256MB

바이러스가 숙주의 몸속에서 1초당 P배씩 증가한다. 처음에 바이러스 K마리가 있었다면 N초 후에는 총 몇 마리의 바이러스로 불어날까? N초 동안 죽는 바이러스는 없다고 가정한다.

입력형식

첫 번째 줄에 처음 바이러스의 수 K, 증가율 P, 총 시간 N(초)이 주어진다.

입력은 다음 조건을 만족한다.

1 ≤ K ≤ 108 인 정수

1 ≤ P ≤ 108 인 정수

1 ≤ N ≤ 106 인 정수

출력형식

최종 바이러스 개수를 1000000007로 나눈 나머지를 출력하라.

입력예제

2 3 2

출력예제

18

도저히 틀린 걸 못찾겠는데,,아무리 고쳐도 계속해서 아래 4문제가 오답이 나왔다... 시간/메모리 초과도 아니고 와 계속해서 고치고 고치고 해도 안풀려서 미뤄두고 있다가 지인의 도움으로...BigInt의 존재를 알게 됨...후...BigInt로 바꿔주니 한방에 해결...으어어어...당연하지만 아직도 모르는게 많구나.

풀이

이번 문제 핵심은 큰 수를 다루는 것인듯.

단순히 모든 수를 곱해 준 후에 마지막에 100000007로 나누려고 하면 수가 오바해버릴 꺼임.

그래서 먼저 찾은 공식이 나머지 분배(?) 공식?이래야 되나. 어릴 때 괄호랑 곱하기랑 섞여있으면 괄호 없애주면서 각자 곱해줄 수 있었던 것처럼

- (X + Y) * m = Xm + Ym

- (X * Y) % m = ((X%m) * (Y%m)) %m

그 후에 BigInt와 같은 존재..(C에서는 double이 되야 하려나.... )를 사용해주기!

코드

var input = require('fs').readFileSync('/dev/stdin').toString().trim().split('

').map(e=>e.split(' ')); // console.log(input) // const K = parseInt(input[0][0]) //처음 바이러스의 수 // const P = parseInt(input[0][1]) //증가율 : 1초당 P배증가 // let N = parseInt(input[0][2]) //총 시간 const K = BigInt(input[0][0]) //처음 바이러스의 수 const P = BigInt(input[0][1]) //증가율 : 1초당 P배증가 let N = BigInt(input[0][2]) //총 시간 // (x * y) % m == ((x % m) * (y % m)) % m let answer = K while(N>0){ N = N -1n answer = (answer * P) % 1000000007n // N-- // answer = (answer * P) % 1000000007 //console.log(N,answer) } console.log(parseInt(answer % 1000000007n))

참고사이트

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/BigInt

https://velog.io/@baemjoon/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8%EC%97%90%EC%84%9C-%EC%95%84%EC%A3%BC-%ED%81%B0-%EC%88%98-%EB%8B%A4%EB%A3%A8%EA%B8%B0-BigInt-7fk5kmrh0n

from http://sbiografia.tistory.com/61 by ccl(A) rewrite - 2021-10-29 19:01:19