서의 공간

[문제]: 1629번: 곱셈 (acmicpc.net) A, B, C가 int보다 작은 자연수라 하더라도, 곱하기 연산을 하는 과정에서 int의 범위(약 21억)보다 커질 수 있다. 따라서 long long 자료형을 사용한 것을 확인 할 수 있다. POWER() 함수의 기저 사례(base case)는 지수 b가 1일 때 자기 자신(a)을 반환한다. 또한, \[a\equiv b\pmod{m} \text{이고 } c\equiv d\pmod{m} \text{이면, } ac\equiv bd\pmod{m} \text{이다.}\] 예를 들어, \[12^{58}\equiv 4\pmod{67}\text{이면 위 식에 의해, } 12^{116}\equiv 16\pmod{67}\text{이다.}\] \(12^{116}\)을..

모듈러 연산(나머지 연산) - 기계인간 John Grib

[문제]: 1697번: 숨바꼭질 (acmicpc.net) #include #include #include using namespace std; int dist[100001]; int N, K; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> N >> K; fill(dist, dist + 100001, -1); // 시작지점 dist[N] = 0; queue q; q.push(N); // 동생의 위치를 찾으면 while문 종료 while (dist[K] == -1) { int cur = q.front(); q.pop(); for (int nxt : { cur - 1, cur + 1, 2 * c..

[문제]: 4179번: 불! (acmicpc.net) 불의 이동은 지훈이의 이동에 독립적이다. 지훈이가 어떻게 움직이든 불은 확산되는 규칙에 따라 계속 확산시켜나가면 된다. 반면 지훈이는 그렇지 않다. 지훈이는 불의 이동에 따라 움직임에 제한을 받게 된다. 이렇게 두 시작점이 서로 간에 영향을 주지 않는 경우라면(현재 불만 지훈이의 이동에 영향을 준다), 두 번의 BFS만으로 해결할 수 있다. 불만 먼저 BFS을 하여 각 공간의 시간들을 구한 후, 지훈이를 BFS 한다. 지훈이가 각 장소에 도착하는 시간과 불이 도착하는 시간을 비교하여 움직임을 제한한다. 추가적인 내용은 코드에 주석으로 달아놓았다. #include #include #include #include using namespace std; st..

[문제]: 7576번: 토마토 (acmicpc.net) 익은 토마토는 여러 곳에 동시에 있을 수 있다. 기억해야 할 것은 시작점이 여러 개인 BFS는 그냥 모든 시작점을 큐에 넣고 BFS 돌리면 끝이다. 방문 되었는지의 여부를 나타내는 배열이 아닌 거리(몇일 걸렸는지 나타내는 시간)를 의미하는 days배열임을 주의 할 것. 깊이가 1 증가할 때마다 days도 1씩 증가한다. #include #include #include using namespace std; int board[1002][1002]; int days[1002][1002]; int dx[4] = { 1, 0, -1, 0 }; int dy[4] = { 0, -1, 0, 1 }; int M, N; int main() { ios_base::syn..

[문제]: 1926번: 그림 (acmicpc.net) 그림의 좌상단에서부터 시작하여 1을 갖고, 방문한 적이 없는 모든 원소에 대해 BFS하면 끝난다. BFS의 기본적인 틀만 기억한다면 쉽게 이해 할 수 있다. area를 계산하는 위치도 눈여겨 보자. if문 바로 안에서 area 변수의 초깃값을 1로 주고 while()문 안에 있는 for()문 안에서 모든 if문을 건너뛰고 vis[nx][ny] = 1; 위 또는 아래줄에 ++area; 해주어도 된다. 다만 시간이 쬐금 더 소모된다. #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nul..

실제 팩토리얼 값을 구할 필요없다. 팩토리얼의 정의를 보면 \[n! = n\times(n-1)\times(n-2)\times\cdots\times 2\times1\] (예) \[10! = 10\times 9\times 8\times 7\times 6\times 5\times 4\times 3\times 2\times 1\] 문제는 일의 자릿수부터 시작해서 처음으로 0이 안나오는 자릿수까지의 0의 개수를 구하는 것이고, 위 식에서 두 수를 곱해서 10이 나오려면 \(10\times 1\)또는 \(5\times 2\)이다. 그러면 결국 나머지 숫자들의 곱에(마지막 자리가 결코 0이 되지 않는다) 100을 곱한 꼴이 되어 0의 개수는 2개다. 이런 식으로 생각하다 보면 0이 추가되는 규칙이 발견되는데, 125..

[문제]: 10826번: 피보나치 수 4 (acmicpc.net) BigInteger 클래스를 만들어서도 풀어보자. operator+()함수의 string 파라미터는 참조형 변수가 아니다. #include #include #include #include using namespace std; // 이 함수는 46번 라인에서 호출됨 string operator+(string str1, string str2) { string ret; int n = 0, carry = 0; // 일의 자리부터 계산하기 위해 reverse(begin(str1), end(str1)); reverse(begin(str2), end(str2)); // 자릿수가 더 적은 숫자 앞에 0을 채워준다. // 예) 254 + 31 -> 254..

[문제]: 14501번: 퇴사 (acmicpc.net) 아아아 #include #include #include #include using namespace std; vector TP; vector dp(16, 0); int MaxRevenue(int n) { int result = 0; for (int i = 1; i N; for(int i = 0; i > T >> P; TP.push_back(make_pair(T, P)); } cout

[문제]: 1463번: 1로 만들기 (acmicpc.net) 숫자가 3의 배수 또는 2의 배수라고 바로 3, 2로 나누어서는 안 된다! 먼저 -1을 한 후의 연산 횟수가 더 적어질 수 있기 때문이다. 10을 예를 들어보면, 10은 2의 배수이니 2로 먼저 나눈다고 해보자. 아래 식은 괄호 없이 순서대로 계산한다(사칙연산 계산 순서 무시). 이때 연산 횟수는 총 4회. \(10\div2-1\div2-1=1\) 하지만, 이렇게 계산할 수도 있다. \(10-1\div3\div3=1\) 이때 연산 횟수는 총 3회. 따라서 주어진 숫자가 3의 배수 또는 2의 배수라 하더라도, 나누기하기 전에 먼저 -1을 한 연산 횟수와 비교를 해야 한다. 먼저 -1을 한 연산 횟수보다 작으면 나누기, 아니면 -1부터. 아래 코드..