백준 9359: 서로소
https://www.acmicpc.net/problem/9359 간단화이 문제는 누적 합을 푸는 요령으로 비슷하게 해결할 수 있다는 것은 금방 알았다.f(x, n) = 1~x 사이에 n과 서로소의 갯수라 정의 하면f(B, N) - f(A - 1, N)으로 간단화할 수 있다. 문제는 어떻게 f(x, n)을 구할 수 있을까다. 소인수분해이것을 구하기 위해서 서로소의 정의를 다시 기억해보자.서로소는 두 정수를 나눌 수 있는 양의 정수가 1밖에 없을 때를 서로소라한다.이 말은 즉, 약수를 공유하지 않는다는 것이다. 그러면, 1 ~ X사이에 특정 수를 약수로써 가진 수는 몇개일까?예를 들어, 2라면? 2, 4, 6, 8, 10 ... 3이라면? 3, 6, 9, 12, 15 ...즉, 특정 약수를 D라 정의했을 ..
백준 1044: 팀 선발
https://www.acmicpc.net/problem/1044 중간에서 만나기푼 보람이 있었던 재밌는 문제였지만, 한편으론 이번에도 사소한 실수로 시간을 낭비해서 그것이 다소 퇴색된 것이 아쉽다. N이 2보다 크고, 36보다 작거나 같은 자연수고, 배열의 원소가 들어갈 지 말지를 결정하는 문제이기에, "중간에서 만나기" 알고리즘을 사용하면 될 것 같다. 일단 이전에 풀었던 관련 알고리즘 문제를 다시 보며, 코드를 분석했다.https://www.acmicpc.net/problem/1208#include #include #include using namespace std;using ll = long long;vector arr1, arr2, s1, s2;int N, S, num;ll ans = 0;voi..
백준 2258: 정육점
https://www.acmicpc.net/problem/2258 이 문제는 얼핏 보면, 가격 순으로 정렬한 뒤에, 앞에서부터 무게를 더했을 때, M을 넘었을 경우 해당 가격이 정답인것처럼 보인다. 그렇게 생각했던 나였지만, 정답률이 낮은 편은 17%인 것을 보니 이것만으로 해결할 수 없을 것 같았다.혹시 이것만으로 해결 못할 케이스가 있을까? 그렇다, 고기의 가격이 같을 경우 위의 아이디어론 해결못한다.예시를 들자면,3 1001 150 250 2이 예제의 답은 4이지만, 위의 아이디어론 2가 나온다. 따라서 가격이 같은 경우를 따로 생각해야한다.그럼, 어떻게 처리해야 할까? 기존 아이디어인 무게를 더하는 것 까지 동일하게 진행하자,해당 가격보다 큰 고기를 살 때, 그 가격보다 작은 고기는 얼마든지 덤으..
백준 2923: 숫자 게임
https://www.acmicpc.net/problem/2923 어떻게 해결하지?모든 A와 모든 B를 짝지어야하기 때문에 가장 큰 수는 가장 작은 수와 매칭해야 최댓값의 최솟값을 구할 수 있을 것 같다.왜냐하면 모든 수를 짝지을 때, 가장 큰 수는 최대한 덜 더하는 것이 이득이기 때문이다. 즉, 다음과 같이 수가 주어졌다면.A: 1 3 5 7 9 B: 2 5 8 11 14(1, 14) (3, 11), (5, 8), (5, 7), (2, 9) 이렇게 매칭한 뒤에, 이 중 합이 가장 큰 15를 고르면 그것이 정답일 것이다. 문제는 라운드마다 수를 더할 때마다. 정렬된 상태의 array가 필요하다. 라운드마다 정렬 시, 시간복잡도는 O(N * N * log(N))N=100,000 라서 시간초과는 불보듯 뻔하..
