본문 바로가기

문제 풀이/백준(BOJ)201

[C++] 백준 1654번 : 랜선 자르기 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 풀이 N개의 랜선을 만드는데 그 길이를 최대로 만들어야 한다. 브루트 포스로 풀 수 있지만 무조건 시간 초과가 발생한다. 이진 탐색으로 탐색 횟수를 줄여야 한다. 가장 긴 길이와 가장 짧은 길이(1) 사이에 답이 존재한다. 이분 탐색을 통해서 그 중간 값과 비교할 텐데 잘랐을 경우 N개가 되는 값이 여러 개 존재한다. 그중에서 최댓값을 찾아야 해서 잘랐을 때 N개.. 2021. 8. 5.
[C++] 백준 10816번 : 숫자 카드 2 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 풀이 숫자 카드의 개수를 구하는 문제이다. map을 구현하면 아주 쉽게 풀 수 있다. 느낀 점 다른 분들은 lower bound와 upper bound로 풀었다. C++ STL에서 지원하기 때문에 아주 쉽게 풀 수도 있다. 나는 보자마자 생각난 게 map이어서 그냥 map으로 풀었다! 코드 #include #include using namespace std;.. 2021. 8. 5.
[C++] 백준 1920번 : 수 찾기 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 풀이 이분 탐색의 쉬운 문제이다. 이분 탐색 시에는 정렬이 되어야 한다는 점만 기억하면 된다! 느낀 점 qsort로 정렬할 때는 틀렸다고 나와서 그냥 sort를 사용했는데 맞았다. 어떤 것이 잘못됐는지 모르겠다. 코드 #include #include using namespace std; int n, m; long long tmp; long lo.. 2021. 8. 3.
[C++] 백준 2740번 : 행렬 곱셈 https://www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 문제 풀이 쉬운 행렬의 곱셈을 구하는 문제이다. 느낀 점 크게 어렵진 않으나 행렬 연산을 줄이는 방법으로 '스트라센 알고리즘'이 있다. 추가적인 공부가 필요할 것 같다. 코드 #include using namespace std; int n, m, k; int m1[101][101]; int m2[101][101]; int m3[101][101]; int main() { ios_b.. 2021. 7. 30.
[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.

티스토리툴바