알고리즘/백준

문제 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 풀이 그리디 가장 작은 자연수인 1부터 N을 넘기 직전까지 더해간다. N이 200이면 다음과 같다. 1 + 2 + 3 + ... + 18 + 19 = 190 다음 수인 20을 더하면 210이므로 200을 초과한다. 여기서 더해지는 자연수는 중복되면 안 되므로, 마지막 수인 19를 29로 바꾸면 합이 200이 된다. 즉, 1부터 더한 값이 넘을 때까지의 자연수의 개수 - 1이 정답이다. 코드 #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); ..

문제 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이 그리디, 우선순위 큐 카드 수가 가장 적은 2개의 묶음을 합치는 방식으로 해결할 수 있다. 이 때, 2개의 묶음을 선택하기 위해, 우선순위 큐를 사용한다. 카드 수가 가장 적은 2개의 묶음을 합친다. 합쳐진 묶음을 다시 우선순위 큐에 넣는다. 모든 카드 묶음이 합쳐질 때까지 반복 코드 #include #include using namespace std; // 오름차순 우선순위 큐 priority_queue pq; int main() { ..

문제 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 그리디 현재까지 지나온 지역 중에서 가장 기름이 싼 기름을 미리 사는 방식으로 해결한다. 현재 지역보다 가격이 싼 지역이 등장할 때까지, 현재 지역에서 기름을 구매하고 이동한다. 이를 반복해서 마지막 지역에 도착한다면 종료한다. // 현재 지역의 오른쪽 지역 중에서, 현재 지역의 가격보다 기름이 싼 지역이 발견되면 다음 목적지로 설정한다. for (int i = current; i ..

문제 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 풀이 그리디 로프들 중에서 무게를 많이 견딜 수 있을 만큼 로프를 골라야 한다. 무게를 많이 버틸 수 있는 로프부터 고르는 것이 최선의 방법이므로, 로프를 내림차순으로 정렬한다. 정렬한 로프를 앞에서부터 탐색한다. i번째 로프에서 최대한 버틸 수 있는 무게는 (i번째로프가 견딜 수 있는 무게) * (i 까지 로프의 수)이다. 이 방법으로 최대 무게를 찾는다. 코드 #include #include using namespace std; int nums..

문제 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 풀이 그리디 기본적인 그리디 알고리즘 문제. 큰 동전부터 거스름돈을 최대한 처리한다. 코드 #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; int change = 1000 - N; int coins[6] = { 500, 100, 50, 10, 5, 1 }; int cur..

문제 2725번: 보이는 점의 개수 첫째 줄에 테스트 케이스의 개수 C(1

문제 10166번: 관중석 KOI 공연장의 관중석에는 가운데에 있는 무대를 중심으로 반지름이 자연수인 동심원(중심이 같은 여러 원들) 위에 다음과 같이 좌석들이 배치되어 있다. 반지름이 1인 원 위에는 좌석이 1개, 반지 www.acmicpc.net 풀이 수학, 유클리드 호제법 좌석을 분수로 생각한다. 반지름이 i이면서 j번째 좌석은 i / j로 표현한다. i1 / j1과 i2 / j2가 기약분수로 표현했을 때, 같은 값을 가진다면, 한 좌석은 다른 좌석을 가리게 된다. D1부터 D2까지의 좌석을 기약분수로 나타냈을 때, 중복되는 경우 답에 추가하지 않는다. 코드 #include using namespace std; // 좌석을 분수로 표현 bool nums[2001][2001]; int gcd(int ..

문제 1188번: 음식 평론가 첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100) www.acmicpc.net 풀이 수학, 유클리드 호제법 소시지를 일자로 이어붙였을 때, M등분 하기 위해서는 길이가 N / M이 되도록 잘라야 한다. 이를 위해선 총 M - 1번 잘라야 한다. 소시지는 일자로 이어붙인 상태이므로, 이미 잘려진 부분이 존재한다. 이 잘려있는 부분이 M - 1번 자른 부분과 동일한 경우, 해당 부분은 자른 횟수에서 제외해야 한다. 이 동일한 부분은 (N과 M의 최대공약수 - 1)개 이다. N이 5, M이 15인 경우, 소시지 하나는 3조각으로 나눠진다. 이 때, 조각 하나의 길이는 1/3이다. 총 잘려지는 횟수는 14번 이며, 이 중 겹치는 부분은 4번이다..

문제 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net 풀이 수학, 유클리드 호제법 입력받은 최대공약수를 A, 최소공배수를 B, 구해야 하는 수를 x, y라고 하면 다음이 성립한다. x % A = 0, y % A = 0 (x * y) / A = B N을 x를 A로 나눈 몫이라고 하면 다음이 성립한다. x = N * A 위 식을 (x * y) / A = B에 대입하면 다음의 결과를 얻을 수 있다. x = N * A, y = B / N y는 자연수 이므로, B / N은 나누어 떨어져야 한다. 그러므로, N은 B의 ..

문제 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 풀이 유클리드 호제법, 수학 완전 탐색으로 하면 시간초과가 발생한다. 주어진 정수 A를 M으로 나눈 나머지가 R이라면 다음을 만족한다. R = A - (A / M) * M 여기서 A는 배열로 주이지므로 다음이 만족한다. R = A[0] - (A[0] / M) * M R = A[1] - (A[1] / M) * M ... R = A[N - 1] - (A[N - 1] / M) * M 문제에서 R이 같은 값이므로 다음이 만족한다. A[1] - A[0] = (A[1] / M - A..