반응형 Problem Solving242 백준 16134번 조합 - C++ 풀이 1. nCr = n! / (n-r)!r! 의 정의대로 계산한다. 2. 나눗셈은 모듈러 곱셈 역원을 이용하여 계산한다. 1. nCr = n! / (n-r)!r! 의 정의대로 계산한다. 조합 nCr의 정의대로 반복문을 통해 계산할 것이다. 2. 나눗셈은 모듈러 곱셈 역원을 이용하여 계산한다. (A*B) mod C = (A mod C) * (B mod C) mod C 임을 이용하여 곱셈을 계산하고, 나눗셈의 경우 1,000,000,007이 소수이므로 모듈러 곱셈 역원을 이용하여 계산한다. 모듈러 곱셈 역원은 분할정복을 이용한 거듭제곱을 사용해서 구하면 된다. #include using namespace std; typedef long long ll; const ll MOD = 1000000007; ll pow.. 2022. 8. 30. 백준 3020번 개똥벌레 - C++ 풀이 1. 종유석과 석순을 따로 저장한다. 2. 이분 탐색을 이용해서 높이 h로 날 때 파괴해야 하는 종유석과 석순의 개수를 구한다. 3. 모든 구간에 대해 파괴해야 하는 장애물의 개수를 구한 뒤 최솟값을 찾는다. 1. 종유석과 석순을 따로 저장한다. 두 장애물의 방향이 다르므로 종유석과 석순을 따로 저장한다. 2. 이분 탐색을 이용해서 높이 h로 날 때 파괴해야 하는 종유석과 석순의 개수를 구한다. 종유석은 끝부분이 h 미만인 것들을 파괴해야 하고, 석순은 끝부분이 h 초과인 것들을 파괴해야 한다. 따라서 종유석과 석순을 각각 정렬한 뒤, 이분 탐색을 이용하여 파괴해야 하는 개수를 각각 구해주면 된다. 3. 모든 구간에 대해 파괴해야 하는 장애물의 개수를 구한 뒤 최솟값을 찾는다. 총 H개의 구간에 대해 파.. 2022. 8. 27. 백준 1744번 수 묶기 - C++ 풀이 1. 양수는 양수끼리 묶고, 음수는 음수끼리 묶는다. 2. 1번 과정을 수행할 때는 수들을 정렬한 뒤, 절댓값이 큰 수부터 차례로 두 개씩 묶는 것이 최선이다. 3. n+1 > n*1이므로 1은 항상 묶지 않고, 0은 음수랑만 묶는다. 1. 양수는 양수끼리 묶고, 음수는 음수끼리 묶는다. 양수와 음수를 묶으면 음수가 되어 묶지 않고 그냥 더하는 것보다 합이 더 작아진다. 따라서 양수는 양수끼리, 음수는 음수끼리만 묶도록 한다. 2. 1번 과정을 수행할 때는 수들을 정렬한 뒤, 절댓값이 큰 수부터 차례로 두 개씩 묶는 것이 최선이다. 이때 합이 최대가 되려면 절댓값이 큰 수부터 차례로 묶어야 한다. 만약 숫자가 홀수개라 마지막 수가 남는다면 그냥 더해준다. 3. n+1 > n*1이므로 1은 항상 묶지 않고.. 2022. 8. 26. 백준 2109번 순회강연 - C++ 풀이 1. 시간 역순으로 매일 가장 강연료를 많이 받을 수 있는 강연을 고른다. 1. 시간 역순으로 매일 가장 강연료를 많이 받을 수 있는 강연을 고른다. 1781번 컵라면 문제와 동일한 문제이다. 13904번 과제 문제와도 동일하다. 1781번 게시글에 그리디 알고리즘에 관해 그림과 함께 설명해두었으니 참고. (강연료 = 컵라면이라고 생각하면 된다.) 백준 1781번 컵라면 - C++(cpp) 풀이 + 그림 설명 1. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 푼다. 1. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 푼다. day일에 풀 수 있 please-amend.tistory.com #include #include #include usi.. 2022. 8. 24. 백준 14391번 종이 조각 - C++ 풀이 1. 각 칸을 세로로 사용할지 가로로 사용할지 결정한 뒤, 전체 조각의 합을 구한다. 2. 모든 경우 중 전체 조각의 합이 가장 큰 경우를 고른다. 1. 각 칸을 세로로 사용할지 가로로 사용할지 결정한 뒤, 전체 조각의 합을 구한다. 모든 칸에 대해 각 칸을 세로 조각으로 사용할지, 가로 조각으로 사용할지 결정한다. 결정 결과를 비트 마스킹으로 나타낼 수 있다. (ex. 가로는 1 세로는 0) 모두 결정한 뒤에는 전체 조각의 합을 구하면 된다. 전체 조각의 합을 구할 때, 인접한 두 칸 A, B가 똑같이 가로 또는 세로 칸일 경우, A와 B는 서로 이어져 있는 긴 조각으로 처리해주어야 한다. 2. 모든 경우 중 전체 조각의 합이 가장 큰 경우를 고른다. 모든 경우를 고려한 뒤 그 중 합이 가장 큰 경우를.. 2022. 8. 23. 이전 1 ··· 8 9 10 11 12 13 14 ··· 49 다음 반응형
