본문 바로가기

반응형

전체 글

(142)
[백준][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 - 문제 두 수가 주어지면 nCm에서 끝자리 0의 개수를 구하는 문제다. - 해설 nCm은 n! / (n-m)! * m!이다. 여기서 끝자리 0의 개수를 구하기 위해서는 1. n!에서 2*5의 개수를 구해서 2. (n-m)!에서 2*5의 개수를 빼고 3. m!에서 2*5의 개수를 빼면 된다. 1. n!에서 2와 5의 개수를 구해보자. 예를 들어 n이 25이라고 하면 25 / 2 = 12 (2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22..
[백준][C++] 3036 : 링 https://www.acmicpc.net/problem/3036 3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다. www.acmicpc.net - 문제 링이 여러개 주어지면 첫 번째 링이 한 바퀴 돌 때 나머지 링들은 몇 바퀴 도는지 푸는 문제다. - 해설 두 번째 링이 첫 번째 링보다 크면 느리게 돌고 두 번째 링이 첫 번째 링보다 작으면 빠르게 돈다는 것만 알고 기약 분수 형태로 만드는 방법을 알면 풀 수 있다. 이 것도 유클리드 호제법으로 풀 수 있다. - 풀이 #include using namespace std; int gcd(int a, int b) { retu..
[백준][C++] 2981: 검문 https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net - 문제 숫자가 N개 주어졌을 때 무엇으로 이 숫자들을 나누었을 때 나머지가 같을 수 있는지 찾는 문제다. - 해설 아래에 주석처리 된 부분이 스스로 풀어 본 건데, 마지막 % 조금 남기고 계속 틀리다고 나와서 찾아봤다. 예를 들어 3,6,34,38이 주어지면 38 - 34 = 4 34 - 6 = 28 6 - 3 = 3 이 나오는데, 이 차를 이용해서 유클리드 호제법을 이용해 최소공배수를 구해준다. 결국 나누었을..
[백준][C++] 1934 : 최소공배수 https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net - 문제 두 수가 주어지면 두 수의 최소 공배수를 구하는 문제다. - 해설 유클리드 호제법이라는 것을 알게 되었는데, 이것을 이용하면 최소공배수, 최대공약수 문제가 쉽게 풀린다. - 풀이 #include #include using namespace std; int gcd(int x, int y) { return (x % y == 0) ? y : gcd(y, x % y); } i..
[백준][C++] 5086 : 배수와 약수 https://www.acmicpc.net/problem/5086 5086번: 배수와 약수 각 테스트 케이스마다 첫 번째 숫자가 두 번째 숫자의 약수라면 factor를, 배수라면 multiple을, 둘 다 아니라면 neither를 출력한다. www.acmicpc.net - 문제 배수인지, 약수인지 둘 다 아닌지 구하는 문제다. - 해설 %를 이용하면 너무 쉽게 풀린다. 이걸 못 풀어서 사람들 풀이를 찾아볼 정도면 기초부터 다시 잡고 문제를 풀어야 하는 게 좋을 것 같다. - 풀이 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); i..
[백준][C++] 1358 : 하키 https://www.acmicpc.net/problem/1358 1358번: 하키 첫째 줄에 수 W H X Y P가 주어진다. P는 선수의 수이다. W와 H는 100보다 작거나 같은 자연수이고, H는 짝수이다. X와 Y는 절댓값이 100보다 작거나 같은 정수이다. P는 최대 50인 자연수이다. 둘째 줄부 www.acmicpc.net - 문제 하키장 모양의 도형의 x,y 좌표가 주어질 때 하키장 내부에 하키 선수들이 몇명 있는지 구하는 문제다. - 해설 1. 중앙의 네모 안에 하키 선수가 있을 경우 2. 좌측 동그라미에 하키 선수가 있을 경우 3. 우측 동그라미에 하키 선수가 있을 경우 이렇게 세가지 경우를 구하면 된다. - 풀이 #include #include using namespace std; in..
[백준][C++] 2477 : 참외밭 https://www.acmicpc.net/problem/2477 2477번: 참외밭 첫 번째 줄에 1m2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1 ≤ K ≤ 20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지 www.acmicpc.net - 문제 ㄱ-자 와 비슷한 모양인 밭에서 자랄 수 있는 참외의 수를 구하는 문제이다. - 해설 total을 통해 1,2,3,4(방향) 중에서 한번씩만 나온 것을 곱해주면 총 사각형의 면적을 구할 수 있고, small을 통해 1,2,3,4 중에서 두 번씩 나온 것들 중에서 사이에 작은 사각형을 만드는 길이들을 구해서 작은 사각형의 면적을 구해 빼주면 된다. 이후에 면적당 참외가 자라는 만큼 곱하면..
[백준][C++] 11478 : 서로 다른 부분 문자열의 개수 https://www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net - 문제 문자열이 주어지면 그 문자열의 부분 문자열 중에서 서로 다른 문자열의 개수를 구하는 문제다. - 해설 substr와 map를 이용해서 쉽게 풀 수 있다. - 풀이 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); string s; map m; cin >> s; for (int i = 0; i < s.size();..

반응형