https://www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net 처음에는 범위가 작은 순으로 먼저 책을 주려했는데 반례가 있다는 걸 깨달았습니다. 책을 원하는 사람들의 정보에 대해 끝 번호가 오름차순이 되면서 끝 번호가 같은 경우 범위가 오름차순이 되도록하면 됩니다. 이렇게 하면 될 거 같아서 해봤는데 맞았네요... 그리디 느낌으로 접근해서 풀이를 어떻게 해야할지 모르겠습니다.... 코드는 다음과 같습니다. #include #include #include #inc..
https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 주어진 입력으로 들어온 보석들을 주어진 가방에 1개씩만 넣을 때 최대 가치를 구하는 문제입니다. 주어진 보석들 중 가방의 최대 무게보다 무거운 애들은 버린 뒤, 보석과 가방을 무게의 오름차순으로 정렬합니다. 그리고 가방의 무게 순으로 넣을 수 있는 모든 보석을 우선순위 큐에 넣은 뒤, 해당 가방의 무게보다 무거운 보석이 나올 때 우선순위..
https://www.acmicpc.net/problem/15711 15711번: 환상의 짝꿍 환상의 나라 디디랜드에서는 인연의 증표로 끈을 하나씩 가지고 있다. 그들은 지극히 평범한 방법으로 이 끈을 이용하여 어떤 두 사람이 환상의 짝꿍인지 판단하는데, 두 사람의 끈을 서로 이 www.acmicpc.net 입력으로 들어오는 두 수의 합이 소수의 합으로 만들 수 있는 지 구하는 문제입니다. 처음에 밀러라빈으로 풀려는데 계속 틀렸다 그래서 에라토스테네스 체로 확실하게 풀었습니다. (아무래도테스트 케이스 중에 수도 프라임인데 합성수인게 있는 듯 하다....) 2,3 은 무조건 안되는 경우, 2보다 큰 짝수는 골드바흐 추측에 의해 두 소수의 합으로 표현됩니다. (아직 참인지는 모르지만 아주 큰 수까지도 성립합..
https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 0 ~ 9 숫자를 1번씩만 사용하여 주어진 부등식을 만족하는 숫자를 만든 뒤 최댓값과 최솟값을 출력하는 문제입니다. bfs를 활용하여 0 ~ 9의 수 하나씩 넣은 벡터에 대해 다음에 들어올 0 ~ 9 의 수를 탐색하며 아직 해당 벡터에 없는 수이면 부등식을 만족할 때 벡터의 마지막 원소로 새로 넣습니다. 그런 다음 최댓값을 갖는 벡터 (초기값 0000..000), 최솟값을 갖는 벡터 (초기값 9..
https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 1,2,3으로만 이루어진 수열 중 좋은 수열의 최소값을 찾는 문제입니다. 좋은 수열은 임의의 인접한 두 부분수열이 동일한 것이 없는 것으로 다음은 나쁜 수열입니다. ex. 33 / 123123 / 12323 1,2,3 3개의 수만 이용하여 구하는 것이므로 빈 string에 1,2,3을 하나씩 넣어보며 나쁜 수열이 나오는 경우 진행을 중단합니다. 1,2,3 순으로 dfs를 진행하기 때문에 가장 처음으로 좋은 수..