본문 바로가기

문제 풀이262

[C++] 백준 11401번 : 이항 계수 3 https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 이전 정수론 단계에서 풀었던 문제의 확장 버전이다. n과 k에 대해서 조합을 구하는 문제인데 n과 k의 범위가 400만이다. 오버플로우가 무조건 발생하기 때문에 1000000007로 나눈 나머지를 구해야 한다. 범위가 너무 크기 때문에 일반적인 방법으로 풀 수 없어 여기서 곱셈의 역원을 이용해야 한다. 곱셈의 역원은 을 만족하는 을 의미한다. 나머지 연산 중 나눗셈에 대해서는 분배 법칙이 성립하지 않아 곱셈의.. 2021. 7. 30.
[C++] 백준 2004번 : 조합 0의 개수 https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 문제 풀이 'BOJ 1676번 : 팩토리얼의 0의 개수'와 비슷한 문제이다. 조합이기 때문에 (N! / (N-M)! M!) 의 2의 개수, 5의 개수 중 최솟값이 정답이다. 이전 'BOJ 1676번 : 팩토리얼의 0의 개수'에선 압도적으로 2의 개수가 많을 수밖에 없기에 5의 개수만 따졌지만 조합에서는 다르기 때문에 어느 것이 작은지 따져줘야한다. 브루트 포스로 해결하려면 시간이 절대적으로 모자라기 때문에 아이디어가 필요하다. N을 K^i로 지속적으로 나누.. 2021. 7. 28.
[C++] 백준 1629번 : 곱셉 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 풀이 브루트 포스로 문제를 풀게 되면 절대 시간 초과가 발생하는 문제이다. 문제를 풀기 위해선 아이디어가 절대적으로 필요하다. 나머지 연산은 분배법칙이 성립한다. 즉, A × B % C = (A % C × B % C) % C 이 성립한다. 함수 pow는 b가 홀수인지 짝수인지에 따라서 연산이 다르다. b가 홀수인 경우는 a를 한 번 더 곱하고 나머지 연산을 한 번 더 해준다. 왜냐하면 a^10은 a^5 × a^5로 한번 더 연산을 할 필요가 없지만 a^5는.. 2021. 7. 27.
[C++] 백준 1780번 : 종이의 개수 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 문제 풀이 이전 문제들과 다르게 4 분할이 아닌 9 분할이다. 이전 문제와 비슷하게 코드를 구현할 수 있지만 '-1, 0, 1'을 조금만 바꾸면 문제가 아주 쉬워진다. 각각의 숫자를 +1 해서 '0, 1, 2'로 바꾸면 카운트할 때도 출력할 때도 쉬워진다. 느낀 점 처음에 이전 문제와 비슷하게 코드를 구현했다. 코드가 길고 썩 깔끔한 구석이 없었다. 다른 분들의 코드를 비교하던 중 아주.. 2021. 7. 27.
[C++] 백준 1992번 : 쿼드트리 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 문제 풀이 이전 문제인 "BOJ 2630번 : 색종이 만들기"와 유사한 문제이다. 쿼드트리를 만들고 맞게 1과 0을 출력하면 된다. 다른 점은 입력받는 방법과 출력 시 '( )'을 맞춰서 출력해야 한다는 점이다. 입력은 공백이 없기 때문에 단순하게 cin으로 받을 수 없어서 string형으로 받고 str [i]가 char라서 아스키코드를 변환하는 방식으로 입력받는다. 출력 시 생성되는.. 2021. 7. 27.
[C++] 백준 2630번 : 색종이 만들기 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 문제 풀이 분할 정복의 첫 문제이다. 함수 div_conq에 x와 y의 좌표를 넣어서 내부에 파란색이 하나라도 칠해져 있다면 4등분으로 나눈다. 함수에서 따지는 cnt의 개수가 0이라면 지금 확인하는 영역이 파란색으로 칠한 것이 하나도 없는 경우이다. 반대로 cnt의 개수가 변의 길이의 제곱과 같다면 확인하는 영역이 모두 파란색이라는 것이다. 그 외에 개수가 애매하다면 .. 2021. 7. 27.

티스토리툴바